They're probably in a cache in your e-mail program's installation folder. If you use Outlook, you'll have to find that on your own. If you use Thunderbird, go to "C:/Documents and Settings/[your username]/Application Data/Thuderbird/Profiles/[random].defaul... Folders/Trash.sdb" and physically delete anything that's in there. Then go to your recycling bin and empty it. If you're using Outlook or some other e-mail client, it's probably still under the Application Data folder, and you'll just have to root around until you find the trash.
To fix the storage problem, you can connect a new, larger hard drive to your computer and install Windows on that drive as well (if you're using Apple or Linux, add on to your question and say so, and I'll give you instructions for those, because everything I've just said is for Windows). When the installation is complete, open up My Compute and open [Size of new disk](E:). Then, highlight everything, right-click, and click "Delete" (this will require Administrative privilages). After you've done this, go back to My Computer, right-click on "Local Disk (C:)", click "Copy", then right click on [Size of new disk](E:) and click "Paste". This will then copy for anywhere between 10 minutes and an hour. Mind you, I've never done this, so I'm not 100% sure it'll work, if someone tells you something else that they're more sure of, go with that. But after you're done, you can shut down, remove your first hard drive, put the second hard drive in its place, and you should be able to boot up normally.