In my case, I have no problems telnetting into localhost 25, but cannot externally.
If you have a router connected make sure you have port 25 forwarded to your Servers internal IP.
If you already have that setup or don;t have a router, then your ISP is blocking port 25, as they are in my case
I have to use the 'relayhost' option in the ISP Server config. Just put your ISP's outgoing mail server there.