Strangely enough, prostitution is actually legal in many places in the U. S....but only under certain circumstances.
What are those circumstances? Simple--a camera of some sort has to be present. Sound weird? Think about it: how is pornography made? Well, somebody pays two (or more) people to have sex while some sort of visual record is made. Now, nothing prevents the director (or whoever's financing the thing) from acting in his own movie. Obviously the director can't meaningfully pay himself, so in effect he's only paying the woman for sex. Now, the production of pornography is legal in many places; thus, you're allowed to pay someone to have sex with you only if you take pictures or movies.
So in a sense, it's already legal. I don't know if anyone has pushed this issue, though ("Damnit, this whorehouse is legal! We have cameras in every room!")