Some email notifications not sending

I recently moved my blog from Hostmonster to another company who uses Rackspace. The move seemed to have went smoothly and everything is up and running, except for one thing. The email notifications I should be getting for comments and moderation do not work all the time. Some of them I get and some of them I do not. There seems to be no rhyme or reason or a pattern to any of this.

A tech who works for the hosting company has been looking into the problem and has been unable to figure it out. He installed WP-Mail-SMTP, but no joy. I have checked and double-checked my settings. Again, no joy. I have four email addresses on this server, based on my domain name, and the other three are working just fine, so I doubt it is a problem with the actual email account.

I suspect something happened during the move from one server to the next, but I am at a loss to understand what it would be. I would appreciate any suggestions you could give me to point me in the right direction.