Heads Up :
The post you are writing will appear in a public forum. Please ensure all content is appropriate for public consumption. Review the employee guidelines for the community here.
Had the same problem with MS Exchange 2k. When you would telnet to port 25 on the outside you would get garbage in 5.1(1), but after adding no fixup smtp 25 it worked fine.