Kenn mich bei Nokia nicht aus, aber guck mal bei den SMS-Einstellungen, ob es da die Optionen "GSM-Zeichensatz" und "Unicode" oder so ähnlich gibt. Vermutlich ist letzteres eingestellt mit dem "Erfolg", dass ein Zeichen aus 16 Bit, statt 7 besteht.

Wahrscheinlich hast du Vokale mit Akzenten benutzt. Nicht alle diese Vokale sind im Standard-7bit-Zeichensatz vorhanden, dann schaltet das Handy automatisch auf den erweiterten Zeichensatz mit den von dir und EHB beschriebenen Folgen um. Man kann allerdings nicht bei jedem Handy den 7bit oder auch reduzierten Zeichensatz erzwingen, da muss man sich bei der Wahl der SOnderzeichen eben zurückhalten und auf Formatierungen und Sonderzeichen (Akzente) verzichten.