I don't have to use Exchange 2007 often, so its quirks are news to me! Here are some things I've found useful lately.
From powershell, run
Get-MailboxDatabase | Clean-MailboxDatabase
This will refresh all of the mailbox stores.
The mailbox has been hidden from the Exchange address lists and you don't know why, but someone still wants to add it. You can unhide, add, and hide it, but since you don't know why it was hidden you can just add it using the full DN.
Get-Mailbox 'Mailbox Name' | fl
Look for the LegacyExchangeDN line and use that in Outlook.