Database Mail Command Not Supported - Again

I have three SQL 2005 servers. Only one will send mail successfully using database mail. The only difference I can see in the way they are set up is that, in the database mail log, the server that works shows a last_mod_by of the domain account that runs SQL Server. The ones that do not work show "sa" as the last_mod_by in the database mail log. It seems that something seems to be trying execute as "sa" rather than as the domain account we wish to run everything. I cannot find where that might be set. I have gone through all the troubleshooting guides and surface area config stuff that I could find and am stumped. Does anyone have any more suggestions I am pointing all three servers to the same SMTP relay, have checked A/V to be sure port 25 blocking is not on, checked the settings in surface area config tool, etc. Anyone have any suggestions Here is a snippet of the latest few records in the log:

86 error 2007-10-24 11:28:46.280 The mail could not be sent to the recipients because of the mail server failure. (Sending Mail using Account 1 (2007-10-24T11:28:46). Exception Message: Cannot send mails to mail server. (Command not implemented. The server response was: Command not Supported). ) 5652 17 NULL 2007-10-24 11:28:46.280 sa

85 information 2007-10-24 11:28:46.187 DatabaseMail process is started 5652 NULL NULL 2007-10-24 11:28:46.187 DOMAIN_NAME\zz_testadmin-test-chy

84 success 2007-10-24 11:28:43.393 Activation successful. NULL NULL NULL 2007-10-24 11:28:43.393 sa

83 success 2007-10-24 11:28:43.377 Activation successful. NULL NULL NULL 2007-10-24 11:28:43.377 sa

82 information 2007-10-24 11:12:21.897 DatabaseMail process is shutting down 6032 NULL NULL 2007-10-24 11:12:21.897 DOMAIN_NAME\zz_testadmin-test-chy

81 error 2007-10-24 11:02:21.907 The mail could not be sent to the recipients because of the mail server failure. (Sending Mail using Account 1 (2007-10-24T11:02:21). Exception Message: Cannot send mails to mail server. (Command not implemented. The server response was: Command not Supported). ) 6032 16 NULL 2007-10-24 11:02:21.907 sa

80 error 2007-10-24 11:01:21.877 The mail could not be sent to the recipients because of the mail server failure. (Sending Mail using Account 1 (2007-10-24T11:01:21). Exception Message: Cannot send mails to mail server. (Command not implemented. The server response was: Command not Supported). ) 6032 16 NULL 2007-10-24 11:01:21.877 sa

Tried that. No joy. Even tried un-installing and reinstalling SQL server (this is a test box) along with SP2. No help there either. My mail guys tell me that no messages get to their SMTP relay. Checked AV to be sure port 25 not blocked. It is OK (McAfee AV Enterprise 8.1.

Database mail does not connect directly to Exchange. It uses SMTP to connect to an SMTP relay mail server, thence to our Exchange server. The mail admins tell me they are not getting anything from the two servers in question. I can ping the SMTP servers. In fact, I can send mail to them using telnet commands, just not SQL 2005 SP2. I am getting mails from other SQL 2005 servers here, but not these two and I cannot figure out why. They all use the same settings, but something is not correct someplace.