A very quick way of blocking spam from botnets is to implement greylisting. This works by passing a ”temporarily unavailable” message to any new email source. Real servers will retry to send the mail after a delay, while botnets will generally move on to another victim.
The default delay on the Ubuntu package is set to 300 seconds. This may cause problems with some legitimate servers, so try adjusting the delay to 10 seconds. This will still defeat most botnets.