Ok guys, looks like it might have been fixed then. Before, the emails were being sent via php. It has now been switched to a smtp method, using a new email account I created. Few tweaks of the backend and we are there!
Half the problem is trying to find out what caused the issue in the first place. Often the host changes things on the server and it kicks stuff out. I figure that is what probably caused the issue in the first place, perhaps some limits on php. There was also an issue with a maximum number of emails sent per hour set to 200. Some of the emails were blocked due to that. So really, it was two issues.