When emails are deleted from your computer they probably are NOT stored on your hard drive.
But the email company probably keep them on a server somewhere, and that is where the police get them from.
I believe Google, for example, keep EVERY email you have ever sent, even if you deleted it months or years ago.
However whether it is possible for YOU to recover and old email from your email provider I don't know.
Try contacting your email provider, though unless you have the exact date (and maybe time) you sent it the may not willing to help (they are not likely to want to trawl through millions of emails to find yours).