I regularly archive my sms by 'moving' them. This way inbox in the phone is always empty and so is sent items. But everytime a send a message manually (without using MPE) i get a "text message memroy over 95% full" error. Sometimes this stops me from sending messages. Even MPE shows full memory free. (option in the others section)
I cant clear any memory because there are no sms in phone. (all archived). and no new sms can come or can be sent. I found a way out by uploading an archived message into phone and manually deleting it in the phone. Then messages can be sent and received. But still the error message appears.
Its a bug of your phone. For the next messages: receive and delete them in the phone itself. After a few messages the internal messagecounter should be refreshed.
I had this same problem with my W810i every now and then. But since I use a K810i, this problem did not occur anymore. Which reminds me that perhaps a software update will cure this problem.