Are the messages in the 'trash' after they are deleted? Or are they simply gone?

Is the user using any other mail clients on different systems?

Is Outlook 2007 configured with IMAP or POP?...