Since everything is revolving around the mail not sending, I'd put a bet against the hosting company you're using and that either their mail server is messed up or their mail server is blacklisted by someone, preventing mails from delivery.
Check logs too and make sure the mail is actually leaving the server.