To start with something trivial: on the PC's where things didn't work, did you check the registry to see if all the entries were properly added? For instance, did the .bat file get run under an account that is actually allowed writing to HKEY_CLASSES_ROOT?
Are any of those PC's running Vista? Could it be they are running the Office suite without UAC, or with a full administrator account? In that case, the entries should be added to the HKEY_LOCAL_MACHINE.
Edit
Ok, if you are sure things are added to the registry properly, next up is RegMon (or procmon if you so prefer). Fire up regmon, start the office host application, and see where it is and isn't looking for the VSTO add-in. Start off with a filter based on your add-in name, then widen up or narrow down depending on the amount of data.