You should be doing this at the router. (Or firewall).
The VM server itself might be a router, depending on your setup.
Unfortunately you'll probably be counting TCP connections per minute, not RCPT TO's per minute. But this doesn't really matter considering the ratio between email rates that a spammer must commit vs someone legit. (far greater than the number of RCPT TO's they can reliably put in one email).
You could require them to use your SMTP server. If they're customers, then it's probably not worth the decreased level of service you're providing even though you're increasing your cost. But if you have a significant spam problem despite reasonable rate limiting, and you switch to extreme rate limiting unless they use your SMTP server (which can do much more in-depth analysis than a firewall), I expect customers to be understanding. If customers are being NATted to the same IP address, asking them to share a single SMTP server is perfectly reasonable (they share an inbound address anyway, they share anti-spam protection risk).