Spyware, a type of potentially unwanted programs (PUPs), has become a significant threat to most Internet users as it introduces serious privacy disclosure and potential security breach to the systems. Current anti-spyware tools use signatures to detect spyware programs. Over time, spyware programs have grown more resilient to this technique; they utilize critical areas of the system to survive reboots and set up mini-installers that re-install a spyware program after it's been detected and removed. Since existing anti-spyware tools are stateless in the sense that they do not remember and monitor the spyware programs that were removed, they fail to permanently remove these self-healing spyware programs. This paper proposes STARS (Stateful Threat-Aware Removal System): a tool that at run time intercepts critical system accesses and assures removed spyware does not re-install itself after a successful removal of spyware program in the system. If a re-installation (self-healing) is detected, STARS infers the source of such activities and discovers additional "suspicious" programs. Experimental results show that STARS is effective in removing self-healing spyware programs that existing anti-spyware tools fail to do.