Desde entonces he comprobado que no se trata de un mensaje push ni de una transmisión celular. Desactivé ambos, pero seguí recibiéndolos. Uno de los dos ya estaba desactivado por defecto, no recuerdo cuál.
Al parecer, al insertar la tarjeta SIM, obtuve una "app" llamada "MTS Menu". Esta es la app que muestra los mensajes. Usando App Master, encontré que esta app viene de /system/app/Stk.apk:
"STK" parece significar Caja de herramientas de la aplicación SIM La tarjeta SIM es una característica que permite a los operadores ofrecer "servicios de valor añadido", también conocidos como bundleware/crapware.
Es realmente estúpido que Android no sólo venga con esta función activada, sino que además haga que el origen de estas ventanas emergentes sea muy difícil de rastrear.