It seems you are not alone on this one.
"THE GOOD NEWS is that as of today (8/26/12), it appears as though they have a solution for it. When you start to type in the letters of the e-mail address and it displays the drop down of choices, you can hover over them and an "x" will appear to the right of each address. When you click on the X you get this message: "The address
xx@xx.com appears here because you've used it regularly in the past. Are you sure you want to delete this email address?" Then click [Delete] and the following message appears --> "The email address
xx@xx.com has been successfully deleted". Then, it really does disappear from the list next time".
I found this solution here.
Mail Help Community on page 6 seventh or eighth post down.
hope this is help to you.