Bitcoin is too geeky for them, and probably worse than cash because they'd need to get their money back through an exchange like MtGox. With exchanges being required to register as MSB's/MTA's, the government might be getting records of all cash people withdraw. Even if the government doesn't get the data, the money has to come out through a bank.

I guess they could do prepaid CC's, but still the prostitute would have to be pretty geeky to want to deal with the hassles involved. Do those prepaid CC's work for everything? I tried to use one to make online purchases once and it wouldn't work.