You've checked a lot of the logical things, and I'll suggest three more:

(1) Shortcut

Right-click the shortcut you use to start Firefox, go to the Shortcut tab, and check the Target line to make sure the URL wasn't added there.

(2) Extension

Add-ons, particularly extensions, can override your own settings. Disable ALL nonessential or unrecognized extensions here:

orange Firefox button (or Tools menu) > Add-ons > Extensions category

Usually a link will appear above at least one disabled extension to restart Firefox. You can complete your work on the tab and click one of the links as the last step.

(3) user.js

External software can create a user.js file which overrides your preferences at startup. This article describes how to track down and remove it: How to fix preferences that won't save.

Any luck?

There may still be something you need to remove at the Windows level.

Does Windows XP let you sort the Add/Remove programs dialog by date? That may help in spotting problem software that has a non-obvious name.

Also, in case you haven't run any supplemental malware scanners, this article suggests a number of free tools that hopefully will help with the clean-up: Troubleshoot Firefox issues caused by malware.

You may also wish to try the searchreset tool

• https://addons.mozilla.org/en-US/firefox/addon/searchreset/