Why don't you build a new server in the same admin group? You can build it online, with a new name and ensure it runs, routes and functions exactly the way you want it. Once everything seems perfect, you can Move Mailbox from the old server to the new server.
When your clients log into Microsoft Outlook, the old server will redirect the client profile to the new machine. As long as you leave the old machine on long enough for users to log in once, this method won't require any end-user touch for the Outlook profile to work correctly.
Once you have all the mailboxes from Exchange 2000 moved to 2003, you can go through steps available from Microsoft on decommissioning your original server.
MEMBER FEEDBACK TO THIS ASK THE EXPERT Q&A:
I believe you meant to say "We have a single server running Windows 2000 Server and Exchange Server 5.5."
If my guess is correct, you have an Active Directory and an Exchange 5.5 directory. There are two paths you can follow. You can either install Exchange into the existing organization (upgrade) or create a new Active Directory and Exchange organization (migrate).
Both methods are perfectly acceptable and supported by Microsoft. The Exchange deployment tool (Exdeploy) can guide you though either process. However, a migration requires the use of the additional tools such as the Active Directory Migration Tool (ADMT) and the Microsoft Exchange Public Folder Migration tool (PFMIGRATE).
The Solution Accelerator for Exchange Consolidation and Migration guide can help you select which method is right for your situation. The guide can accelerate the design, planning, and deployment of Exchange Server 2003 messaging systems deployed as upgrades to, or replacements for, your existing Exchange Server 5.5 systems.
For more information, visit the Microsoft Exchange Server 2003 Upgrade TechCenter.
Do you have comments on this Ask the Expert Q&A? Let us know.
Related information from SearchExchange.com:
Dig Deeper on Exchange Server setup and troubleshooting
Related Q&A from Peter Tersteeg
If recently created mailboxes are not displayed in the GAL after a migration to Exchange 2007, Active Directory (AD) has yet to replicate the ... Continue Reading
If you are migrating mailboxes across domains after an upgrade to Exchange Server 2007, you will need to update the Exchange Management Console. Continue Reading
Discover the complications that could arise from installing Exchange Server 2003 and the domain controller on the same hardware. Continue Reading