We've just upgraded from 2.2 to 4.0 ourselves so maybe I can help.
What I did for the upgrade was gradually upgrade the handheld code on all the devices first to 4.0, this still allowed my users to continue with the service till the new server was in place..(obviously they will need to resynch with desktop manager or on the server after the new code has been applied)..
Once I had installed the new BES 4.0 I simply selected to import the relevant users from the old legacy server and assigned each an enterprise activation password and off they went.. there were no issues with mail redirection at all, the only thing you may want to keep an eye open for is that your mail sweepers allow in the enterprise activation mail sent to the relevant user when activating...recieved from a etp.eu.blackberry.net address or something with an attached .dat file...
apart from that the migration was as smooth as a babies ass
Hope this helps anyway