I've reconsidered on Spitzer. As I said, he's done nothing that should be illegal. The motivation for criticism against him is that he prosecuted people for various victimless crimes, including prostitution, and is therefore a hypocrite. That turns on whether his role as a prosecutor should have been to follow the law, his conscience, or the will of the electorate - the old question of representative government. I no longer strive to strive towards such things, so the case for me is a question of corruption rather than hypocrisy.
But what's the accusation here? This is a politician with considerable power, who it seems has been paying for sex with his own money. He didn't put some bit of fluff on the payroll, funnel contracts to her, lean on some quango to put her down as a consultant, or pay her out of some slush fund extracted in the course of ordinary corruption. He went to an ATM and drew $4300 from his personal bank account. If that's not indicative of an unusually honest politician, what the hell is?
There can't be any doubt about it, since that's how he got caught. If he had paid for sex with taxpayers' money, like so many of his peers, he would probably have got away with it. That's not a paradox: governments spend so much money, and get so little in return, that bonus services are easy to hide.