Are you sure you are looking at the right thing now ?
I had the Auto-complete cache issue several releases ago, but have not experienced it recently.
In my experience the "forget" logic works correctly. But, one of the major sources of confusion is that you cannot "forget" an email address that is still in your "Emailed contacts" list.
I have found that if there is a "bad" email address that consistently crops up during auto-complete, finding and deleting it from the "Emailed Contacts" folder, and then clearing the trash drops it.