Assuming the deleted items folder is located on the Exchange server, it seems something is wrong in the communication between Exchange on the server and Outlook on the client: Exchange reports the presence of a non-existing file in that folder, when Outlook asks for it.

It doesn't seem to be an Office/Outlook problem. So contact the system manager administering the Exchange server. Maybe a simple reboot there will help.

Kees