I think this is an issue with the hosting provider. Maybe you have reached a send limit or maybe the SMTP server has issues. Who is your hosting provider? Are you on dedicated or shared hosting? Can I get access to the admin control panel to see if there are any email logs I can look at?