I am having exactly this problem (just two years later).
When I arrived on this site 6 months ago I was able to easily restore individual mail messages. Nothing has changed (except for a few password changes and a couple of updates (both BE and WS2003)) and now I can no longer drill down any further than mailbox store in the restore wizard or ordinary restore.
(i.e. I used to be able to get server/information store/mailbox store/mailbox/top of store/inbox/message, now I get server/information store/mailbox store/none).
The check box for "restore individual items" is still checked. I have tried creating new backup jobs with exactly the same result.
I am running Exchange 2003, WS2003 and BE11dSP2.
Any help would be very gratefully received.
Ben