YES, all exchange versions will run in an AD 2003 environment. Exchange 5.5 has an ADC specifically for an Exchange 5.5/ AD 2003 environment.
The best way would be to setup the new ADC (from SP1 to avoid problems). Then if there’s a need, install a new Exchange 2003 server. Then move users from 5.5 to 2003.
I have heard of Upromote, but I have no experience with it, so I cannot tell. Personally, I’d rather install a fresh copy of NT4.