I've had to reinstall FF twice because it was slowing down, both times fixed it.
Just to make sure, after you uninstall it, do you remove reminants from program files and any FF registry entries?
Has worked for me on xp, might want to try a firefox message board if this doesn't fix it.