What is the reason for mail not being sent / non-delivery that is listed in the mail queue against each mail that is listed there? What do the logs say?
You have described the issue, but we need the appropriate log entries to be able to help.
Check the mail queue and if the status is either “deferred” or “bounced” there’s a high likihood that your SMTP traffic is being blocked by your provider.
However, this is just an educated guess, more information including some entries from your log would go a long way in helping you further.
Why is mail not being sent? You need to look at the relevant log. Our mail troubleshooting guide tells you where to find the logs, and probably how to troubleshoot this problem (we’re happy to help, we just need more information).