"Text message memory full" But already deleted all threads...

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 applications/application manager, try deleting the cache settings for the app. NOT user settings, but cache only.

Also, while in settings, check you internal memory space.

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.