hmmmm, i hate it when that happens:(
you already said it (and you said it didn't work) ... but i'll say try again ... reinstall it and then uninstall it. try to reinstall from a different source.
when you uninstall, use revo uninstaller (if 32 bit) or Advanced Uninstaller Pro (32 and 64) or wise uninstaller (32 and 64). they will scan for left overs to remove for you.
or use wise registry cleaner (advanced uninstaller pro also has a registry cleaner in it). scan system and look only for entries that say opera mail or something. only select them to delete. make a retore point first (you can make a registry back up with these two registry cleaners first/also).
one more possiblity: since opera mail is in opera presto. perhaps if you install the browser and uninstall it, it will remove the mail parts for you. this might get you around the problem you're having with reinstalling the mail program.