I had this "Yahoo! Address AutoComplete" entry in my "Add or Remove Programs" that I cannot remove. Whenever I select to uninstall this item, the item blinks but never got uninstalled. There are some postings in the internet, but none of them solves the problem.
I looked into the registry and found something like this.
C:\WINDOWS\System32\regsvr32 /u C:\PROGRA~1\Yahoo!\Common\yaddbook.dll
My wild guess is that the missing yaddbook.dll is causing the uninstallation to fail. I downloaded yautocomplete.cab (which contains yaddbook.dll), unzip the contents into the folder C:\Program Files\Yahoo!\Common.
Now the "Yahoo! Address AutoComplete" can be uninstalled. It is now gone !!!