The issue we were experiencing was that my WordPress installation was not able to send email to Hotmail and Mailinator email accounts. It was sending them just fine to Gmail and Yahoo email accounts.
Quite literally, the emails were disappearing. There was no record of them being lost. No bouncebacks.
After testing and checking all sorts of things [spam filters, SMTP, mail(), plugins, etc., etc., etc.] we discovered the problem was that our IP was blacklisted.
Basically, email companies use different algorithms and services to determine what messages belong in spam, what messages belong in trash, and what messages get into the inbox. Unbeknownst to me a few hours ago, it is also possible that emails will go to none of the above. They will literally just be lost without a trace. Amazingly frustrating.
To solve the problem, we first made our way to mxtoolbox.com and used their blacklist checker. We were on the blacklist for 2 out of the 105 in their list. But aparently those two are big ones. I don’t even remember which lists they were.
We had to go to the blacklist manager tools for each of those two lists and request a de-listing. Within an hour emails were flowing like the Mississippi in August.
All in all, the problem took not to long to solve once we knew what the problem was, but I bet we spent 40 hours trying to get there.