There's often a lot of unknowns in situations such as this and so one of the first steps when troubleshooting such an issue is to check if your ISP is blocking port 25.
This can be done very easily by trying to connect to your server on port 25 using telnet and seeing what response you get back. If you see anything relating to your ISP, or more specifically anything that doesn't look like its coming from your SMTP server, then your ISP will be blocking port 25. This is also assuming that you don't get any errors, timeouts or the like.
Here's how to do it on a Windows-based PC from the command prompt (although any telnet client would do just as well):
Code:
telnet example.com 25
An average Cpanel server running Exim will then respond in a following fashion (this is what my server responds with):
Code:
220-example.com ESMTP Exim 4.44 #1 Mon, 14 Mar 2005 10:49:48 +0000
220-We do not authorize the use of this system to transport unsolicited,
220 and/or bulk e-mail.
If you get a valid response back (i.e. not a timeout or any other error) and it refers to the name of your ISP, they are blocking port 25.