Can't uninstall firefox beta release on Windows XP as you discribe
I can't uninstall Firefox 8 beta on my Windows XP as you describe. It appears "Your computer must be restarted to complete a previous upgrade of Firefox. Do you want to reboot now?" Rebooting does not solve the problem. When installing a new version the same message appears. When checking for updates appears "Firefox is up to date".
Computer must be restarted message after Firefox upgrade
If you see a message similar to Your computer must be restarted to complete a previous upgrade of Firefox after a major update (e.g., from Firefox 3.6 to 8.0) and restarting the computer doesn't help: On Windows, open the Mozilla Firefox installation directory (e.g., C:\Program Files\Mozilla Firefox or, on 64-bit Windows, C:\Program Files (x86)\Mozilla Firefox) and delete the file "firefox.exe.moz-upgrade". If you still can't start Firefox, do a clean reinstall (use another browser to download the Firefox installer from www.mozilla.org/firefox and, after first removing the Mozilla Firefox installation directory, reinstall Firefox).
The above refers to an error attempting to start Firefox but the same solution might work for errors when attempting to uninstall Firefox (delete the file firefox.exe.moz-upgrade from the folder where Firefox is installed, then run the uninstaller.) See also Uninstall Firefox from your computer.