Alla fine avevo "risolto" reinstallando il firmware del cellulare e rimettendoci solo le App che utilizzavo, e il problema non si è ripresentato. Avevo anche contattato il 119 (tramite Twitter) e non risultavano abbonamenti attivati ma solo alcuni SMS verso numerazioni che credo fossero anche inesistenti.

Secondo me era qualche App che tentava di mandare SMS a numeri "premium" locali di qualche altra nazione, ma poi non ho più approfondito.