First of all, as has been noted by other posters, regulation (i.e. the government restricting certain activities) is completely consistent with a libertarian, free market ideology. Indeed, a free market depends on government intervention.
A free market depends on exchanges that are voluntarily entered into by all sides, and no one (well ok almost no one) doubts that the government can and should step in to prevent coercion, fraud, theft, murder, etc. When one party does not pay the full cost of its actions, i.e. externalizes those costs (or as the economists say, “imposes an externality”) then there is a good argument for government intervention.
So, people are not allowed to drive down my street blasting loud speakers (whether they are advertising or not), because while it may benefit them, it imposes costs on everybody else.
Ok, but enough of that, the interesting question is, should the government keep out of regulating telemarketers and see if the free market comes up with a better solution? I think there is a similar question regarding spam email.
One of many factors that makes this complicated is that, until very recently, phone service was a local monopoly (and still is in many areas.) It’s not as if there are 10 phone companies competing for your business. If there were, perhaps you would see them offering various creative means to block unwanted calls from telemarketers.
I wonder, for example, about a system that would let me set up the following contract: I will only take your call if (1) you are on a pre approved list (which would include government numbers, etc.) or (2) you put up a “bond” of 25 cents (or some other fairly small figure.) Then you as a telemarketer can decide whether it is worth it to call me and risk my forcing you to pay me 25 cents.