Hi there! I am using the original Droid and use the Handcent SMS app for messaging. I am not receiving incoming texts and have the error message stating that my message memory is full. I just deleted all threads about a week ago so this was surprising, but regardless I deleted again. I double checked both messaging and handcent and both are empty. The only answer I can think of is that I have some kind of backup storage setting, but I can't find it anywhere on my phone!
Thank you in advance!
In my case (dell venue), it was the huge amount of system logs that were using up the internal memory.
I cleaned up /data/systemlog directory using 'adb shell' then the internal memory increased from 40MB to 450MB and the phone started to run fine.