The trick is that you don't delete auto-complete entries from the main Thunderbird window -- you delete them from the auto complete cache as accessible from within a new email. * Turn auto-completion on * How - go to main Thunderbird window, Tools, Address Book, Tools, Options, make sure Automatically add outgoing e-mail addresses to my: (I use Collected Address).
Open a new email * Within the email window, click View and select the Contacts Sidebar (will place a check by it) (should create a pane at the left with the list of addresses) * Delete the entry you don't want. You may have several Address Books that you may have to search to delete all entries you don't want to pop up when typing a name in your To: bar.
I've done this successfully on my machine.