Are you running McAfee? The basic installation of McAfee blocks port 25 by default. You can disable this in the console under access protection the top check box.
One way you can rule out your ISP is by using another email application like quick mailer http://pyric.org/qm/ this is a lightweight stand-alone email application. You will have to enter your SMTP server to send a test message.
Are you able to telnet to your smtp server? From a command prompt type in ‘telnet smtp_server_name_or_ip 25’
here is s funny short story, i work at a cable company help desk, guy calls in, cannot send email, swear up and down that he quadruple chekc every thing, turned out he typed SMTP >STMP and also curse me saying that that how it used to work before, funny story after he listen to me and rearrange the letters. i was not beside him but i know he was red in the face.
Point to this is check the server setting again and verify the correct port.