Ну, тем не менее какой-то почтовый сервер должен использоваться для отправки и, судя по тому, что этот сервер не дает релеить почту внешним получателям, это один из ваших почтовых серверов. Т.е. вам необходимо на том почтовом сервере, который используется вашим внешним сайтом, разрешить релей для писем приходящих с IP-адреса этого сайта.