So McAfee did not remove it at all? I just paid $89.95 for nothing?
Not true. These fake anti-malware work in such a way that none of the antivirus applications can catch them easily.
There is no such thing as a 100% malware-proof machine, so arm your self with some extra antimalware applications such as Malwarebytes or SuperAntispyware, but only use the free versions as the poaid ones often clash with antivirus applications.
A removal guide here will help as this fakeware belongs to the same category: http://www.bleepingcomputer.com/virus-removal/remove-win-7-internet-security-201 1
McAfee also has an application called GetSusp which has had much success against these fake antimalware pests. Join THIS group if you want to find out about it.