URL rewriting is not happening with IE(which now takes a very long time to start) so I checked the extensions in Firefox and found something called “XULRunner 1.9.1” which I certainly didn’t install after I reinstalled Firefox a few days ago. Removing Disabling it has seemingly fixed the URL rewriting in Firefox on the infected PC for now. Still need to figure out how to remove it.
Support.mozilla.com indicates that this may be Trojan.FakeAlert i.e. one of the viruses removed about 5 days ago.