Nakonec na všechno pomohlo nové zaregistrování knihoven. Kdyby se s tím někdo potkal, pomůže následující:

Obecně: regsvr32.exe [jmeno_knihovny]

Konkrétně (Některé ani v PC nejsou a nebo nejdou zaregistrovat, toho si nevšímejte, nevadí to. Sepsal jsem všechny, které se alespoň trochu týkaly problémů s IE 5 nebo 6 a úspěch se dostavil ):
regsvr32 actxprxy.dll
regsvr32 asctrls.ocx
regsvr32 browseui.dll
regsvr32 cdfview.dll
regsvr32 comcat.dll
regsvr32 comctl32.dll
regsvr32 corpol.dll
regsvr32 cryptdlg.dll
regsvr32 digest.dll
regsvr32 dispex.dll
regsvr32 dssbase.dll
regsvr32 dssenh.dll
regsvr32 dxtmsft.dll
regsvr32 dxtrans.dll
regsvr32 gpkcsp.dll
regsvr32 hlink.dll
regsvr32 icmfilter.dll
regsvr32 iepeers.dll
regsvr32 iesetup.dll
regsvr32 imgutil.dll
regsvr32 inetcpl.cpl
regsvr32 initpki.dll
regsvr32 inseng.dll
regsvr32 jscript.dll
regsvr32 licmgr10.dll
regsvr32 mlang.dll
regsvr32 mmefxe.ocx
regsvr32 mobsync.dll
regsvr32 msapsspc.dll
regsvr32 mshta.exe
regsvr32 mshtml.dll
regsvr32 mshtmled.dll
regsvr32 msident.dll
regsvr32 msieftp.dll
regsvr32 msjava.dll
regsvr32 msnsspc.dll
regsvr32 msr2c.dll
regsvr32 msrating.dll
regsvr32 msxml.dll
regsvr32 msxml3.dll
regsvr32 occache.dll
regsvr32 oleaut32.dll
regsvr32 pdm32.dll
regsvr32 plugin.ocx
regsvr32 pngfilt.dll
regsvr32 proctexe.ocx
regsvr32 pstores.exe
regsvr32 rsabase.dll
regsvr32 rsaenh.dll
regsvr32 sccbase.dll
regsvr32 scrobj.dll
regsvr32 sendmail.dll
regsvr32 setupwbv.dll
regsvr32 shdoc401.dll
regsvr32 shdocvw.dll
regsvr32 shell32.dll
regsvr32 slbcsp.dll
regsvr32 softpub.dll
regsvr32 tdc.ocx
regsvr32 thumbvw.dll
regsvr32 urlmon.dll
regsvr32 vbscript.dll
regsvr32 webcheck.dll
regsvr32 wininet.dll
regsvr32 wintrust.dll