If you have a CDMA Curve it's a regular problem not related to file free memory regardless of what anyone else posts. The problem does not exist on GSM BBs. Delete your SMS history and the problem will go away until you start texting that person a lot again.
Posted from my CrackBerry at wapforums.crackberry.com
u dont gotta delete ur messages completly. this problem happens to me about twice a day.
when your going to send a message click ur menu key like if u were gonna send the text and click remove history and then send it and itll be fine for a little while