Quanto ao AV nunca ouvi falar.. só testando é que tiro conclusões
Se for melhor que o gratuito AVG já é muito bom (duvido um bocado mas não sei).
Quanto a FW.. olha que teres a do xp ou não teres é praticamente a mesma coisa. Lá pela ZA se chata e pesada não quer dizer que outras o sejam. Se está inclinado para as soluções freeware experimenta sygate ou a kerio (recomendo 4.1.3 e não as mais recentes). Unicamente precisas de gastar algum tempo a configurar para não ser chata e bloquear tudo.
Aos anti-spywares talvez acrescentasse o Spy Swepper ou o M$ anti-spyware (eu uso o Spy Bot mas não apanha tudo portanto em equipa é muito melhor

) e o Spyware Blaster tambem é recomendável, principalmente a quem usa frequentemente o IE.
PS: Esse *.exe que não conseguiu remover deve ter sido porque esse ficheiro devia estar em utilização no momento, possivelmente algum trojan. Entre em modo de segurança e corra novamente o AV, aí já deverá remover
