Sending e-mail is done through port 25. There are many ISPs that block this to combat spam, as Art said.
An incomplete list of ISPs that block port 25 include...
AT&T, MindSpring, BellSouth, MSN, CableOne, NetZero, Charter, People PC, Comcast, ATTBI, Sprynet, Cox, Sympatico.ca, EarthLink, Verio, Flashnet, Verizon, and MediaOne.
After you press Start and then Run on Windows and enter "telnet://[emailserver]:25" (without quotes), you should receive a 220 response code.
Your host may be able to set up an SMTP server with different ports.
EDIT: Check out the following for more info.
http://www.postcastserver.com/help/P..._Blocking.aspx