> I'd bet good money that you have a compromised or vulnerable mailer script on your machine somewhere

This must be the case. I turned on SPF and DKIM and the spam emails slowed down for a while, but are now back in full force.

It looks like I will need to torch the whole VPS (I have backed up the important data)