We have sort of resolved the issue.

We had been using a local account to run SQL Server.  When we switched to a domain account, the problem vanished!

This proves that it...

We have made some progress.  We had been using a local account to run the SQL engine.  Switching to a domain account made the problem vanish!

This indicates a trust/domain networking...

Yes, the login exists.

It is some kind of network/firewall/protocol something, probably caused by the emphasis on security in Windows Server 2003.

I am looking for a clue to figure out...