Exchange 2007 – Forward outbound mail to external SMTP server

What you're doing won't do what you want. Adding a secondary SMTP proxy on a user won't cause that user to be able to send email that shows as coming "From:" that secondary address.

To do what you want you need to create a group object with the desired "secondary address" and grant the user "Send As" rights on the group object. Make the user a member of the group.

In order for the group to be able to receive replies from the Internet, modify the properties of the group by going to the "Mail Flow Settings" tab of the group properties and the "Properties" for "Message delivery restrictions". Uncheck the box "Require that all senders are authenticated".

Edit: Because I'm an idiot, I was only thinking about sending. I modified the above such that a group is used and, because the user is a member of the group, replies will be sent to the user.

Rather than poking at a black box and wondering why it won't work, install "Network Monitor" or Wireshark on the SMTP relay machine and sniff some SMTP traffic. You'll find out in about 30 seconds why your mail is being rejected. That's going to be your path of least resistance. The box wants to tell you what's wrong, you just need to look.

Your "network engineer" should've reached for the sniffer earlier, IMO. Sniffing the traffic on the wire seems "taboo" to some people, but it's often the best way to get to the bottom of a problem in a human-readable protocol like SMTP.