I get the low space message with what seems like a fairly limited number of apps installed, caches cleared and as much as possible pushed to SD ... what is the actual capacity there? HTC Incredible in my case ...
This app is great if you're rooted. https://market.android.com/details?id=com.aac.cachemate.demo...
Otherwise, I find AppBrain great to be able to easily see space usage and move stuff to SD.
I have a Samsung Galaxy Spica (not S, a european phone), and the limit is at about 15 MB when I get warnings. That's hundreds of SMSes... Then again, the Gmail cache eats MBs like a dog eats dogfood: easily 3MB.
Similar situation here, I recently freed up several mb's as well; but nonetheless started to receive the low space notification again a few days later (not having installed anything in the meantime).
The fact that this subsequently results in missed SMS messages is inexcusable IMO.