Thanks for raising this issue. I'm not really sure whether this is something that we can easily, or should really fix within Moodle. To be honest, it seems that your host has implemented this rate limiting in a strange way. It is the job of the Mail Transfer Agent (MTA) to transfer the messages you pass it to the next point in the queue. If the MTA is unable to deliver them immediately, it is *meant* to queue them until such a time that it can send them.
Moodle does not handle these kinds of failures well - it has no way of doing so as it was never really designed with this in mind. In the case of forum emails, we have a single flag for each discussion - if you have 100 users subscribed to the same discussion, we only mark that discussion as sent once - not once per user.
If you really want to hack Moodle to do this, then you can do so - it is Open Source after all, but this is not a change that I would be keen to support.
The easiest way to hack this into Moodle is to edit lib/moodlelib.php - Find this line: https://github.com/moodle/moodle/blob/v2.9.1/lib/moodlelib.php#L5657, and just before the "return true;" line, add a sleep(2).
As I say, I don't think that Moodle is the best place to perform this kind of rate limiting, and that you should persuade your host to re-consider the way in which they rate limit e-mail. Perhaps they could whitelist certain domains for example.
Hope this helps,