I received a HoMM4 disks from a friend who is no longer playing the game (which I love to play) but when I try to us the patch it gets halfway and then says it has found a file by the same name and can't continue and no patches were updated. I have verified that I am using the UK version and am using the UK patches. I have version 1.o.o.1 if this helps.
I had similar problems. I uninstalled and deleted all of it, rebooted, reinstalled, re-downloaded and installed patches in order found from ToH's site, and then it worked fine. Never found a logical explaination, but it worked.