I don't know much about notes and how that upgrade would go. We have exchange and personally, I would rather upgrade the mail servers before the BES. That way, as long as you have a good DB, you can always just build a new BES. But again, I don't really know how easy or complex the mail upgrade would be, so I could be wrong.
As for the licensing and migrating, you don't have to buy a new license. I called up RIM and told them I wanted to upgrade my server, they gave me a 3 month Temp SRP for testing, and a 3 month Temp SRP for migrating users. Then they gave me the FTP to them that had all the software (BES5.0 all MR's, and all SP's, and the transporter tool). We build the new server, migrated a few of us to test and play with it, and then migrated all our users. Your CAL's can work on both as long as you are in a migration process. The only thing you need is the temp SRP.