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.
CAUSEThis issue occurs because the Windows Server 2003 security templates are more secure than the Microsoft Windows 2000 security templates.
RESOLUTIONTo 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.
Network access: Allow anonymous SID/Name translation
Network access: Do not allow anonymous enumeration of SAM accounts
Network access: Let Everyone permissions apply to anonymous users
Network security: Do not store LAN Manager hash value on next password change
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.