We have a similar problem... We are looking for all solutions inside and outside Moodle.
Can you tell me what was the origin and/or the solution for your problem? Even if it is not related to Moodle. Any advice is welcome!
our moodle front servers were configured with two dns servers.
The first of them was down, so for each message sent, there were a 5sec timout before joining the second DNS server. (DNS used for our smtp server)