Any cluebats?
Not sure if it will help your specific situation, but you could look into server side "grey listing". This will cause your mail server to temporarily reject mail from them, forcing them to try again a couple hours later. Fly-by-night spam places almost never bother to resubmit, so it's pretty effective (it cut down my spam to under 5% literally overnight).
https://en.wikipedia.org/wiki/Greylisting
