I had a mailbox that wouldn't let the user delete emails, even though permissions were correct (I recently had to recover my exchange files using eseutil due to quarantine of a log file). So, I exported the mailbox to a pst (from Outlook), deleted the mailbox on the server, recreated the mailbox on the server, and importing the pst (using Outlook).
When I email that account, I am now getting the email bounced back to me as:
"The e-mail account does not exist at the organization this message was sent to. Check the e-mail address, or contact the recipient directly to find out the correct address."
Everything appears to be setup correctly. What am I missing?