You didn't post what operating system you are using. If you are using ME or XP, you can try doing a system restore to a time prior to the OE uninstall. If that doesn't work, look in the recycle bin and see if somehow it ended up there. If it is in the recycle bin, you can restore it there. AdAware does have the option to hold deleted files in a quarantine list. If it is OE is there, see if you can cancel the deletion.
If neither of those options work, you are probably out of luck retriving your old mail. You can download a new copy of OE from Microsoft.com, add your ISP settings and get your account running again. Outlook Express downloads mail to your hard drive. And unless you have it set to leave a copy of your mail on the server, that mail is lost when the program gets uninstalled or corrupted.
While uninstalling some spyware, I accidently clicked uninstall Outlook Express. Since I have yet to reboot, I am hoping that I can cancel or avoid the uninstallation. At worst, is there a way to save the old emails and contacts?