Looking at the log files, it seems that outgoing emails from the new server were being blocked by some providers (AOL being one).
I have switched to an external mail delivery service to get around this and it seems to be working ok now.
Keep me posted if you feel you're missing any notifications.
Thanks,
Q