Disappering emails and folder

The issues: A missing subfolder of Inbox and disappearing email.

Start of Issues: Monday, July 14, 2008 and Today, July 22, 2008

Maintenance Prior to Issues: Installation of Exchange and other server updates, including reboot (July 9, 2008).

Things I have checked:
All Software is up to date
Verified all filters are off and removed all but one rule.
Verified mail is being sent to Mailbox - User and not Personal Folder
Verified mail items have not been archived.
Verified folder has not been moved into another folder.
Looked for e-mails and folder in OWA - e-mails were there, folder "P" was not
Looking in Spam and Junk E-mail folders - not there

Other details:
Both issues seem to isolated to one client, the rest of the office is fine.

I was out off the office when the missing folder issue occurred. Starting last Monday, the user was unable to see file folder normally located at Mailbox -- Inbox -- Folder "P".  User is able to use the "move to folder" button to find and use the folder "P"; however if the user does a search for documents within the folder, the search comes up blank.

The disappearing mail issue happened today.  At approximately 11:15 PDT, the user received two emails from senders X and Y. The user opened, read both e-mails, forwarded sender Y's email, then the returned to the Inbox to find the both emails gone.  Shortly after the incident, another e-mail came from sender X, however this one did not disappear after it was read. I checked with the recipient of the forwarded sender Y email, and the recipient did received it.  As stated above, I used OWA and I was able to see both emails in the Inbox.

Question:  How do I recover/replace Folder "P"; and why did this happen?  How do I recover/replace e-mail's from X & Y to the user's client Outlook Inbox?