If message tracking says it was delivered locally to the mailbox, then it was delivered.

You should check to see if anything else could have affected the message after it was delivered.  For instance, check if there is any client-level antivirus or antispam running on the client desktop that interact with Outlook.

Have you enabled the DumpsterAlwaysOn registry key, and then checked "Recover Deleted Items" for both Inbox and Deleted Items?