I'm disappointed that the 1.1.1 update does not address the issue for users on an Exchange server where items deleted on your iPhone do not delete on the Exchange server - but are instead left on the server and shown as "read".
I cant help you with the why, but this issue IS fixed for me after the update. Prior I had the same issue, and was also unable to move mail from folder to folder. It would move on the iPhone, but not when I went back into my outlook. Now both work.
I use themessagecenter.com for my exchange hosting. I noticed after the update settings in my mail account on the phone that either were not there, or I just never noticed. Either way the advanced settings show port 993 for incoming, and port 587 for outgoing. This was not entered by me. SSL is on for incoming, and off for outgoing.
Hope this helps. I was resigned to the fact that the iPhone did not support this fully, but after the update I am glad it works. There do not seem to be many people concerned with exchange support so it is hard to find info. Let me know if you need me to look at other items to see why its working for me.