Ok, that's the problem.
When you delete an email, it doesn't go to your desktop recycle bin. It goes to a deleted items folder within outlook. Those emails are online and not locally stored on your computer.
The only thing that goes into your desktop recycle bin, are items stored locally on your PC or removable drives, that you delete.