First off, all the mailboxes are being backed up, they are just not showing up in the catalog. If you were to restore the information store to a Recovery Storage Group you would be able to find the user you are looking for in that store.
But as to the issue you are having.
What revision of BE11d are you running and what patches do you have installed? (check this from Help - About)
Are you backing up to tape or to disk?
If you have updated BE, did you also update the remote agent on the Exchange server if it is remote?