Exchange 2003 and OWA

I am running Exchange 2003 with SP1. I have a user that deleted over two thousand messages while in the office using Outlook 2003. He also deleted thos messages out of his deleted items. When he went home that night and logged onto the system using Outlook Web Access, those two thousand messages were still there. It has been over a week now and those messages are gone when he is in the Office using Outlook but still show up when he logs in using OWA.
Any help is greatly appreciated.