Kann keine Nachrichten mehr versenden

Ich kann mit meinem Handy (Nokia E51) seit einiger Zeit keine SMS-Nachrichten mehr versenden. Die Nachrichten bleiben im Postausgang und werden nicht gesendet. Wählt man sie danach an, so bekomme ich eine Fehlermeldung die mir sagt dass ich nicht mehr genug Speicher hätte und dass ich es dann nochmal versuchen sollte.
Sowohl Speicherkarte als auch Sim-Karte habe ich bereits komplett gelöscht. Handy aus- und wieder anmachen, sowie Reset und alle sonstigen einfachen möglichen Problemlösungen habe ich natürlich auch schon ausprobiert.
Kann mir jemand weiterhelfen? =(

Telefonieren sowie SMS empfangen funktioniert übrigens noch

Für Hilfe danke ich im Vorraus

Überprüfe mal, ob Deine Einstellungen zum SMS-Versand noch stimmen (Kurzmitteilungszentrale, etc.). Zur Sicherheit kannst Du Dir auf der Nokia-Webseite die Einstellungen auch bequem per SMS schicken lassen - such da mal auf der Produktseite des E51 nach dem Handy-Konfigurator.

Den besagten Handy-Konfigurator kann ich weder auf der Produktseite des E-51, noch irgendwo anders auf der Website finden. =(

Stellen sich diese Einstellungen nicht auch dann zurück wenn ich das Handy auf Werkseinstellungen zurücksetze? - Das habe ich schon ausprobiert - leider wie gesagt ohne Erfolg.

Die genaue Fehlermeldung wenn man die Nachricht im Postausgang anwählt lautet:
- Allgemeiner Speicher voll
- Alle Programme schließen
- Nochmals versuchen

Der Konfigurator ist hier: -http://www.nokia.de/service-und-software/konfiguration

...aber Dein Problem hört sich eher danach an, als wäre der interne Messaging-Speicher voll. Eventuell mal ein paar SMS löschen?

Die SMS habe ich bereits alle gelöscht, das funktionierte nicht.

Was muss ich mit diesem Konfigurator jetzt genau machen?