Well, I have run the sfc /scannow 3x, with no errors showing, done an AV scan with no infections and uninstalled/reinstalled MSXML4 SP3 with no positive result. I have also reinstalled the affected programs.
I can't imagine what's keeping the programs from seeing it.