sms - Message Memory Full, Incoming message rejected

I got this message on my phone:

Message Memory full
Incoming message rejected

I have deleted a lot of messages, and I have also run the memory cleaners I have on my phone.

What should I do?

Exactly which memory is used?

Are there alternate apps that will let me store the messages in a different location?

Answer

According to several sources (including a.o. TechniPages and AndroidCentral) the cause of this problem is lacking space in your device's internal memory, which must have at least 25MB free space left.

T-Mobile's support pages have a detailed instruction on how to solve the issue. Though for some steps it was not clear to me what Android version (and what menu option) they were referring to, as a basic abstract the most important points include:

• Remove apps you no longer need
  This is the fastest solution, as it will certainly reclaim larger amounts of space per single step. To do so, you can e.g. use Androids default app manager: Go to Settings → Applications → Manage Applications, select the Downloaded tab (you only can remove apps you downloaded yourself), check which apps you no longer need, tap their entry, and hit the Uninstall (or Remove) button. In case this is grayed out, you might need to Force Stop the app first.


• Move apps to your sd card
  This option is available with Android 2.2 and higher, but doesn't work with all apps. In short, apps must actively support this -- and must not provide widgets and some other things in order to be moved to sd card. The built-in "mover" only permits you to move apps applying to these rules.


• Cleaning up caches
  You can do so manually going to Settings → Applications → Manage Applications, select "All" (not just "Downloaded"), tap each app, and select the Clear Cache button.



• Clear history
  This is for your call-logs etc. I doubt this reclaims lots of space.

Having followed these essential steps (which I placed in the order of "most effective first"), your problem should be gone.