You need to look at the authentication on your SMTP server. I have had this problem before, where my application cannot send mail due to rely rules ect. The easiest would be to add your primary server's ip as a trusted server in your postfix config.
I presume you have tested your postfix and knows it is working? Have you tried to telnet in from an outside ip and send a mail? This will give you decent debugging information to resolve your problem.