I do not have any issues with my exchange and I do backup to tape. I still backup the mailboxes as well, mainly because I have plenty of room on my tapes and plenty of time to perform the backup, I understand that not everyone has that luxury.
I originally had heaps of problems but in the end I removed all the carry over backup selection lists and jobs that were carried over from V10, as well as all the pre installed policies so that my pallette was blank. I then created a new selection list and lo and behold, it worked.
I did smite it hip and thigh.