The reason it might not be removed permantly is because you have your system restore on before running these programs turn off system restore then run them to remove it.
To turn off system restore right click my computer go down to properties and left click,click on system restore tab at top and check the box for turn off system restore once system restore turned off run spybot search & destroy and ad-aware and delete anything they find once finished put system restore back on.
John
April 2005