Aún no existiendo los virus como tal y recomendándose que ante todo se use el sentido común y la precaución en lo que se instala, puestos a tener algo que pueda funcionar yo uso el Comodo antivirus, es el más completo que conozco, es gratuito y viene con firewall (necesario root), anti-theft, administrador de apps (backups y desinstalador), optimizador de sistema y batería, blacklist y muchas más cosas... así que al menos vale la pena, creo yo.
También he visto hablar bien del que comentan más arriba, el Dr web light, pero ese aún no lo he probado.
Que extraño todo eso, estando de baja los servicios premium y hecho los wipes correspondientes ya debería haberse solucionado, es como volver a tener un móvil nuevo. Me inclino también a que sea una suscripción fortuita en algún servicio, ya sea a través de un juego, sms de concurso o lo que sea. Intenta hacer memoria o estudia bien el contenido de los sms que envía, ahí debe dar la pista del fin que busca y qué está detrás. De todas formas y para quedarte más tranquilo, flashea una nueva rom stock con sus correspondientes wipes también, pero sobre todo eso, averiguar como sea el origen de todo eso.
Suerte.