1. This might be your phone. The database which holds the messages has an index problem which causes old messages to re-appear.
Or...
2. Do you use an SMS programme? that may need an update or bin it/change it.
Or...
3. Delete old messages on a regular basis!