Вы наверняка регились на сайтах,указывали свой почтовый ящик. Спам скорее всего идёт на ящик,а ваш андроид сам проверяет почту наличие сообщений и выдаёт в виде СМСок.
Это исключено. Во-первых, смс-ки посылает явно не почтовый агент, это было бы видно. К тому же у меня почтовый агент проверяет наличие почты только по моему запросу (так он настроен). Во-вторых, прослеживается явная корреляция тематики смс-спама с теми сайтами, которые я посещал (только посещал, не регистрировался) непосредственно перед тем, как стал его получать. Регистрируюсь я (с указанием почтового ящика) в исключительно редких случаях на надёжных сайтах. А телефон вообще не указываю никогда принципиально (по этой причине меня, в частности, нет "в контакте").
Ещё я грешу на Adobe flash. Может быть с его помощью можно узнать телефон?