I have not read the guide posted above but this is what I would do.
Load Win2k3 server on the new system as a new install. Setup the new Active Directory domain using Microsoft default of companyname.local and make sure not to active DHCP if your WinNT server has it running. Configure DNS and Exchange recipient policy to allow the reception of your email domain (ex. company.com). Then re-create all the same users in the new Active Directoy and with mailbox auto creation.
Next depends on the number of users. If you have only a few have the users backup their Exchange 5.5 inbox to individual PST files. Have the user log into the new Active Directory (join new domain) and Import them to the new Exchange 2003 inbox. If you have a lot of users research the Exchange 2003 resource kit for a migraiton tool.