Is it possible to run 4.0 on your desktop and handheld while still using Mailstreet or other MDS that is running 3.6? If so, is this advisable?

Yes..I do that right now.. You just don't get to use all the features of 4.0

I'm trying to add the BB service to my Mailstreet account, if the rep would call me back.

I added the BES online - I think most of their services get added directly online.

I went ahead and added it online too. But they now tell me that I need to call and schedule an appointment to get the software installed with a technician on the telephone (?!!)

Actually its pretty painless. You download a remote control client similar to PC Anywhere (can't remember the name) and the technician sets your computer up for you while you watch. You can set it up youself, but it's better to let them do it. I set it up myself but had a couple of settings wrong, which the tech corrected. Takes about 30-45 minutes.