Rozwiązałem problem po przez użycie aplikacji Handcent, która służy do pisania, odbierania smsów. Podczas wysyłania wiadomości, aplikacja usuwa wszystkie polskie znaki wstawiając w ich miejsce odpowiednio l, a, s, itd.
W moim przypadku aplikacja znacznie ułatwiła wysyłanie wiadomości i pozwala zaoszczędzić kilka groszy na smsach.
Dla instalujących ten program, w celu uniknięcia kolejnych pytań lub poszukiwań odpowiedzi, dodam, że po zainstalowaniu programu należy wyłączyć powiadomienia o przychodzących wiadomościach w systemowym programie zarządzającym wiadomościami. W przeciwnym razie będziemy otrzymywać zdublowane informacje o nowej wiadomości.