I assume reinstalling Windows managed to remove the program then?

In general I'm unimpressed by software which requires a dedicated tool to remove, though probably more so because most instances I've come across of this are to do with spyware.