For XP you can download the PowerToys from Microsoft by Clicking
Here. In this package is something called Tweak UI. With that program you can remove items that are lingering in your Add/Remove programs listing. Once you remove it from there XP "should" be able to reinstall it.
Did you happent to crash during your uninstall? I know windows has this error on occasion.. but usually its pretty rare to happen.
Let us know how it goes.