I've seen this where it's a name resolution problem for the server. LMHOSTS is the file you need for netBios name resolution. HOSTS is for DNS.
Are you running WINS? If so, check the database for correct Exchange server mapping.
Name resolution is done at boot up. Name checking is done in this order:
Check whether the queried name belongs to the local machine.
Check the local name cache, which by default retains resolved names for 10 minutes.
Direct a point-to-point query to the configured WINS server or servers.
Use a broadcast query.
Use a local LMHOSTS file, if one exists.
Use a local HOSTS file, if one exists. (A HOSTS file resides in the \%systemroot%\system32\drivers\etc folder on Win2K or NT systems or in the Windows folder on Win9x systems.)
Issue a point-to-point query to any configured DNS serve.