Thunderbird Deleted all my Deleted Items!

It's not the double-negative that it sounds like.  I "delete" all my emails (that have been actioned) so they go into my Deleted Items folder in Outlook, for reference at a future date.

However, I then started using Ubuntu at work meaning Outlook was no longer an option.  There is the Outlook web view, but as far as I can tell there's no search feature.  Being the modern techno-geek radical that I am, I thought Thunderbird would be a good idea, at least for the search facility.

Initially it went well, but then I noticed that the contents of my deleted items had disappeared: 5 years worth of emails (about 9,000 emails in all)!

The problem seemed to stem from the fact that I had "Empty Trash on Exit".  I naively thought that this meant it would empty the Trash folder on exit, but Thunderbird, presumably trying to be clever and helpful, decided that my "Deleted Items" folder was my trash, not the actual Trash folder.  Er, thanks.  Back to Outlook it is then.  I just hope I can recover them all.