Emails Missing From Outlook 2003

Got a call for help from a work colleague that has left me stumped. He uses Outlook 2003 to pick up his email, not from an exchange server unfortunately. He somehow managed to move all his emails into the deleted items folder. He then highlighted them all and tried to move them back into the inbox. He says that an email then appeared on his screen with all his old emails as attachments. Because he didn't want to send thousands of old emails to anyone else, he closed that email down. Now he can't find his old emails anywhere. I've looked but can't find them either, does anyone have any ideas or have they gone for good?

Thanks in advance!