When you say you deleted an email from the users mailbox, did you delete just the shortcut ? have you tried checking
http://evservername/enterprisevault/search.asp
or
http://evservername/enterprisevault/archiveexploterui.asp
Does the mail exist in either of these ?
Or what about
Do you archive your mail journal, would the message exist in the journal archive ? was the message sent any other users ?
HTH