I’m not an Exchange expert but I do know that in order to work properly the Exchange server needs a Global Catalog (GC) for name checking, etc. There seems to be an issue when you upgrade this GC to Windows Server 2003:
After you upgrade the global catalog to Windows Server 2003, you receive an error message when you use Outlook 2000 or an earlier version to resolve aliases or to connect to a server that is running Exchange Server (KB903295)

SYMPTOMS:
You upgrade the global catalog to Microsoft Windows Server 2003. When you use Microsoft Outlook 2000 or an earlier version to resolve aliases by clicking Check Names, you receive an error message that is similar to the following:
The name could not be resolved. Network problems are preventing connection to the Microsoft Exchange Server computer. Contact your system administrator if this condition persists.
Alternatively, when you use Outlook 2000 or an earlier version to connect to a server that is running Microsoft Exchange Server, you receive an error message that is similar to the following:
Exchange Server is unavailable.

CAUSE
This issue occurs because the Windows Server 2003 security templates are more secure than the Microsoft Windows 2000 security templates.

RESOLUTION
To resolve the issue, follow these steps:
1. On the global catalog that was upgraded to Windows Server 2003, click Start, point to All Programs, point to Administrative Tools, and then click Domain Controller Security Policy.
2. Expand Local Policies, and then click Security Options.
3. Set the policies as listed in the following table.

Policy Name

Status

Network access: Allow anonymous SID/Name translation

Enabled

Network access: Do not allow anonymous enumeration of SAM accounts

Disabled

Network access: Let Everyone permissions apply to anonymous users

Enabled

Network security: Do not store LAN Manager hash value on next password change

Disabled

Network security: LAN Manager authentication level

Send LM & NTLM response

4. Close the Domain Controller Security Policy console.
5. Click Start, click Run, type gpupdate /force, and then click OK.
6. On the Exchange server, click Start, click Run, type services.msc, and then click OK.
7. Locate the Microsoft Exchange System Attendant service, click Restart Service on the toolbar, and then close the Services console.

 

Greetings, Daniel