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.