You know how you used to advertise prostitutes before the internet? You found a pay phone in a seedy area. You write the number on the walls of every truckstop/bar/porn store bathroom you can find. Then you camp outside the payphone (using your menacing glare to prevent others from using the phone). Then, when guys call you, you setup the deal and meet them there. There's no way to trace it (not like you own the payphone).
My point is, I don't recall any open letter to US West or "Ma Bell" begging them to make it harder on these people.
Guess what, the way you cracked down on prostitution then is the same way you do it now, stings and undercover work. Rather than suing Craig's List (as one sheriff once tried to do), you should be using it to catch these criminals. They are right there, begging to be caught, and rather than track them down, you go after the website that "makes it a little easier".