Does your provider allow you to send mail through another server that is not owned by them? Alot of ISP's block port 25 on their networks.
So you could try submission ..
uncomment the submission lines in master.cf of your postfix installation, then restart postfix and try to connect with port 587 instead of 25 (i think you need to enable TLS as well on the client)
|