@Simon:

This is on Exchange 2010. Steps to repro:
1. Get an email (shows both on the phone and Outlook)
2. Open it on the phone, delete it
3. Check outlook, it'll show "Deleted Items (1)" with the newly deleted item being unread when I read it on the phone.

I just got my phone hooked up to our Exchange server and I have the exact same issue with deleted emails, they are all marked unread even after opening them before deleting.