iOS has a messages limit. It's 15 MB - if you go over it the messages will be automatically deleted.
The best thing to remedy it is to manually delete threaded messages that you don't longer need.
When I called Apple Support, I had two different people yesterday tell me there is no limit and no messages should delete themselves.
Secondly, I have a 32 GB iPhone 4S and I have almost 28 GB free. I realize you're talking 15 MB and not GB, but still, I have plenty of space.
If there is in fact a 15 MB limit for messages, someone needs to tell Apple Support because they apparently don't know. Each of the people I talked to put me on hold and checked with their supervisor and came back to say there wasn't any kind of limit for messages.
I'm going to call an Apple Store today and see if I get a clearer answer. If it's 15 MB, then so be it, I can deal with that. But don't tell me there's no limit if there is.