"Das Programm läuft, ohne installiert worden zu sein."
"Das Programm läuft selbst dann noch, nachdem ich es gelöscht habe."

Das klingt für mich irgendwie nach einem schlecht geschriebenen Wurm. Ich würde dir auch dazu raten, dein System zu scannen - am besten von einem als sauber bekannten Bootmedium (beispielsweise einer Live-CD) oder vom Inernet aus (fast alle AV-Anbieter bieten einen Onlinescan, du mußt nur viel Zeit mitbringen).
Und vielleicht solltest du Geld in einen NAT-Router investieren. IMO sollte kein Windows-Rechner ohne NAT an's Internet.