Symptoms

A certain user has an Exchange mailbox listed in POA Control Panel, this means that mailbox was created by means of POA.

When logging in to OWA (Outlook Web Access) as user with Exchange mailbox, the following error message is displayed:
Outlook Web Access could not find a mailbox for DOMAIN\username. If the problem continues, contact technical support for your organization and tell them the following: The mailbox may be stored on a Microsoft Exchange 2000 or Microsoft Exchange 2003 server, or the Active Directory user account was created recently and has not yet replicated to the Active Directory site where this Client Access server is hosted. or A problem occurred while you were trying to use your mailbox.
Using EMC (Exchange Management Console) or EMS (Exchange Management Shell) on Exchange server mailbox for the user cannot be found either.

Cause

Mailbox has been removed directly in Exchange.

Resolution

If mailbox has not been completely deleted on Exchange server yet you can try to follow Microsoft's guide on reconnecting a disconnected mailbox: http://support.microsoft.com/kb/274343.

Otherwise, the only viable options are restoring mailbox from backup or recreating a mailbox from scratch on Exchange server or in POA Customer Control Panel.