A couple of points I should clarify with my previous comments:

1. I am using an IMAP account on my Q to sync with my Exchange server.
2. When I verified the email was still there I was using Exchange OWA to connect to my server and see the email I deleted in my deleted items in my mailbox.

The reason I am using IMAP is that I also sync via ActiveSync to my work Exchange server. This is the only solution I can figure to use since MS does not allow 2 separate Exchange AS profiles.