I would get the 3.6 BES to new hardware, upgrade to BES 4.0 then move the mialbox. The reason why is BES 3.6 stores the users in the mailbox and BES 4.0 stores them in the database.
In the instance that something happens during the maibox move you could lose the users and have to reactivate them all.
Once you're on BES 4.0 the DB is the most important part to keep safe. You can create a new BESAdmin everyday and jnot affect the users, unless you setup the account wrong
Exchange versions will not matter between BES 3.6 and 4.0 as well.
I would install the Exchange 2003 System tools on the new hardware which also inlcudes the 5.5 administrator and apply SP2 for Exchange 2003 as well to ensure that the BES is matching you're Exchange Server. The BES needs to be at the same level or higher then you're Exchange Server to ensure proper communication.
Once you've moved the mailbox update permissions and the MAPI profiles. Nothing to it
