So user1 is trying to open user2's mailbox, pure exchange 2007 environment, all patched, SP1, etc.. User2's mailbox says that user1 has full access.
So the exact error from outlook was "The name cannot be resolved. The name cannot be matched to a name in the address list." I assumed this was an outlook issue, deleted profiles, etc.. Nothing I did seemed to help, this was where I got frustrated and needed a new direction.
For troubleshooting I opened OWA logged in as user1, tried to open user2's mailbox, it says that it could not be found. I could open that mailbox logged in as myself through OWA and Outlook, and so could my two test user accounts. Very weird, user2's mailbox is a legacy account from Exchange 2000, 2003, but it doesn't make sense. After quite a bit of troubleshooting, moving the mailbox to other information stores, even detaching the mailbox and creating a new mailbox, no luck. I went into ADSIedit, checked all the properties, it was NOT hidden from the GAL.
Finally, I just deleted the user2 AD user2&mailbox. Created a new windows user2, reattached the original mailbox to that user, and after about 20 minutes of sync time, it worked and user1 was able to see user2's mailbox again.
So the issue was with User2's AD account, not the mailbox. Hopefully if it happens again I can nail it down a little more.