While looking into your problem I found that I had the same thing. I finally found this page click here which gives the same info as already supplied by Stuartli but in a litle more detail. I've just tried it and it worked for me. Don't confuse the Delete key with Delete that is usually available through right-click.
Greengage. I think that you may have misunderstood what Ambasedor is asking for. He only wants to remove previously deleted email addresses which stubbornly persist in the autofill entries that dropdown when you start typing in the 'To' field. He doesn't want to delete his email account.