JimT, there's a free program called Restoration which will recover all deleted files from your H/D providing they haven't been overwritten by other data. Can't remember where you download it from but someone will be kind enough to tell you in a moment
Deletion of emails in not like deletion of normal files, as emails are not files.
Emails are held in a database - each folder is one file (database) with all the emails (records) in it.
When you delete a record (email) from any database (inc email folders), the record (email) does not get removed, it gets taken out of the index file - the index file governs which records (emails) you actually see on the screen.
The only way to actually remove files from a database is to compact it - early versions of OE did not do this automatically, and so even though your (say) Inbox did not show many files, you could often find it was very large - open it with wordpad and you could see lots of old emails in it. Newer versions seem to compact automatically.
Now compacting a database does not mean that the data removed is lurking on the disk as recoverable files - it ain't.
So basically, if it isn't in Deleted items, and the folders have been compacted, you're out of luck.
The only thing you can try is to open the relevant folder with a text program (say, Wordpad), and see what you find.