Use Revo Uninstaller and it will clear it out and take care of all the left behind registry entries as well. I took SAS off my PC some time ago because it always froze my PC half way through. PS It is free and there was an update a day or two ago.
I had Super AntiSpyware and followed their intructions to get rid of it - which was to do exactly as you have done using the Add/Remove tool. I found - like you - that Super AntiSpyware was still on my desktop and still in my Programs menu, and there was still an empty Super AntiSpyware folder in my Program Files.
I have now manually deleted all of these entries and left it at that. No doubt it is still in the registry but that's for a registry cleaner to sort out.