Maybe thats why it's called stealth, lol!
Sorry, bad joke.
I had the exact same problem with a game I thought I'd uninstalled. Each time I went to put it back in, it said I needed to uninstall the old version. Eventually I lost the plot and re-installed XP and it never happened again. Might have been a coruption in the registry. So maybe a Regcleaner might sort it, but don't quote me on that.
Someone more knowledgeable on here will put you right, but I'll be watching this post cause I'd like to know how to solve it myself.