SpamCop/Blacklisting - This is actually very effective. I lookup the IP address of every email and check it against these databases. A failure has its session terminated immediately. The vast majority of the entries in these databases are from infected computers sending spam.
So here's something I've never understood: if zombies are such an issue, why aren't the ISPs taking action? It's their bandwidth being gobbled up too.
I would expect that network traffic from compromised machines would match some simple heuristics (high-speed, repeated http requests for DDOS, many non-local SMTP connections for outgoing spam, etc). If a machine trips the heuristics, knock the client off with an http redirect instructing them to contact support). Whitelists could keep online those few legitimate users who trigger the blocks.
This would probably never fly with commercial and high-end users, but I'm assuming Joe Sixpack (and Grandpa Sixpack) are the bigger problem. What am I missing? Or is this already happening?