It is important that you should upgrade to the latest revision.
Click on Help -> About and verify the revision number.
If you have 11.0.6235 then you need to download revision 11.0.7170
Once the backup server is at 7170, run Liveupdate to get the current hotfixes, then deploy the remote agent back to your Exchange server.
Run a full backup of Exchange and then you should see all mailboxes in the restore selections.
--------------------------------------------------------------------------
Note** All the mailboxes were backed up since they are included in the entire Information Store. The reason you cannot see them in the restore tab is due to an Active Directory setting.
Eventhough there is Hotfix 11 for revision 6235 - you should upgrade to 7170 (which includes this fix)