Hidden sms message sent at every startup
Sounds more like a virus. The only guarenteed way is to flash a fresh ROM and start over. Malware is getting smarter and smarter and may be able to hide itself on the OS unless you start fresh.