I'm scraping the bottom of the barrel on this one - I know that some malware protection programs "clean" the windows registry by actually removing "unwanted" entries. If the required entries are not in the registry then turning off the firewall won't help. I have absolutely no idea how to check if this is actually the case, but if it is indeed the case, then the solution is fairly obvious - stop the malware protection and reinstall SW
If the problem was/is caused by the malware protection program, then it's a bit like a bladeless knife without a handle - the operation was a success but the patient died.
I use WinZip malware protection and I'm pretty satisfied with it. When it discovers problematic entries in the registry it gives details and allows us to electively not remove it. Unfortunately (or fortunately) I've never needed to use this feature.