It's still with us, I just checked with a machine that has not been updated yet.
That fix is an independent fix and switching from IE 5.5 to 6.0 sp1 or installing
other updates should not have any effect on it. However the uninstall process must
have left the files (or traces of them) on your system, so it does not try to install
it again. But looking at the uninstall procedure, it looks like it would have removed
all traces of it. Not sure why it is not trying to install it again unless it is
seeing it in the Windows Update log file.
I would still like to see a HijackThis log of the system, to see if there is anything
that might have been causing a conflict with the KB891711 fix.