The email you received was the one that you have to respond to before your key is available on the Global Directory for download. Periodically there after (I think it may be six months), you will recieve a new key verification letter - if you don't act on this one, the key will be deleted from the server.
In order to delete your key from the web interface for the Global Directory, you must have PGP installed, and must have the private key available to prove that you are the owner of that key. Re-installing PGP will not help if you don't also have the private key.
I don't believe there is any other way to delete your key. However, in the past it was possible to email customerservice@pgp.com to explain your situtation and ask for a manual uninstall. I'm not optimistic this will work now, but you may want to give it a try.