That sounds like a fairly serious problem. I have three things that you might try while waiting for someone with better ideas.

1) Delete the firefox folder entirely. Don't rely on the uninstall tool, just wipe it out. Maybe try the uninstall tool after that, if it can still recognize that FF is on your computer.
2) Run more scans. Super Anti Spyware and Malware Bytes are both good ones.
3) Try to reinstall without uninstalling. I don't know what happens when you do this for firefox, but a lot of times you'll be given a "repair installation" option.

No idea how helpful the above suggestions are, but I figured some sort of response was better than none.