A ver... Si reseteaste de fábrica no puede ser ninguna aplicación del móvil.. fin del tema por ese lado.
Lo que puede ser es que estés dado ya de alta en un servicio premium y te siga manando mensajes.
Primero como dice un compañero llama a tu compañía y prohíbe los mensajes premiun, de paso que cancelen esa suscripción. Desde el móvil ya no se puede hacer nada más.
No existen virus en Android por lo que los antivirus no sirven para nada.
Lo que tenéis que hacer es cuando instaléis una aplicación de fuera del marquet mirar que permisos pide...