Recently had an SBS2011 Server with Exchange 2010 bring up SMTP Errors of

554 5.2.0 STOREDRV.Deliver.Exception:StoragePermanentException.MapiExceptionCallFailed; Failed to process message due to a permanent exception with message Cannot open mailbox

The DB was mounted fine and I could create new users

Mapi would not connect via Outlook 

Opening the mailbox in OWA would bring : 

Exception
Exception type: Microsoft.Exchange.Data.Storage.StoragePermanentException
Exception message: Cannot query rows in a table.

This was for all users

In the end I had to 

Dismount DB

eseutil /p “C:\Program Files\Microsoft\Exchange Server\V14\Mailbox\Mailbox Database\Mailbox Database.edb”

You can try mounting the database. If it mounts, you are good to go, if it doesn’t you have to check the logs:

Check and Repair the database logs

2. Check the exchange logs (don’t forget to specify E00 – the starting sequence for the logs)

eseutil /ml “C:\Program Files\Microsoft\Exchange Server\V14\Mailbox\Mailbox Database\E00”

2.a There will be a list of logs and depending on their state, you may get an error. (They should all say OK, if the logs are clean) Errors vary, but most likely it is a file corruption and needs a chkdsk to run.

As a sidenote, if the database state is Clean Shutdown you can safely remove the logs.