You're not going to like this any better than the answer you have now (unhide and re-hide), but specifying the
legacyExchangeDN of the user's mailbox will allow "Check Name" to function even if the object is hidden (since, basically, that's what "Check Name" is doing-- resolving the user's alias into the legacyExchangeDN).
My "EAnderson" user on my test rig here has a legacyExchangeDN of "/o=Home/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)/cn=Recipients/cn=EAnderson". I verify the that mailbox is hidden from address lists, won't resolve with the alias name "EAnderson", but "Check Name" works fine and the mailbox opens when I use the legacyExchangeDN. (This trick has worked all the way back to at least Exchange 5.5 and was a trick I'd use to show people who though they were "Exchange experts" that, perhaps, they didn't know everything they thought they did... heh heh...)
Where do you get the legacyExchangeDN? Using a tool like ADSIEDIT will let you see it, as will any other tools that allow "free form" queries of the Active Directory database.
Once you know the format of your users' legacyExchangeDN attributes you can probably formulate them out of your head. They've gotten a lot uglier in Exchange 2007 because they have the reference to the "/ou=Exchange Administrative Group (FYDIBOHF23SPDLT)" AG in them.