Block port 25 by default
If the ISPs hosting these botnet-infected machines blocked port 25 (as many/most UK ISPs do), the spam couldn't spread anywhere near as easily. Most spam my mailserver receives comes from domestic connections outside the EU/US which are clearly from botnet infected machines that shouldn't be operating a mailserver.