SMS messages changing position sound really strange, and I'm not sure it was what actually happened. Read all my answer to discover what I think could be the actual explanation.
TL;DR: you are lucky, because you can free your SMS memory with a single command: AT+CMGDA.
According to AT command guide its syntax is really simple:
AT+CMGDA=<type>
where <type> has a different meaning according to the +CMGF setting.
In text mode (after AT+CMGF=1):
"DEL READ" - Delete all read messages
"DEL UNREAD" - Delete all unread messages
"DEL SENT" - Delete all sent SMS
"DEL UNSENT" - Delete all unsent SMS
"DEL INBOX" - Delete all received SMS
"DEL ALL" - Delete all SMS
In PDU mode (after AT+CMGF=0, that's not actually required, as it is the default value):
1 - Delete all read messages
2 - Delete all unread messages
3 - Delete all sent SMS
4 - Delete all unsent SMS
5 - Delete all received SMS
6 - Delete all SMS
What you need is to provide
AT+CMGDA="DEL ALL"
if you are operating in text mode, or
AT+CMGDA=6
if you are operating in PDU mode.
Even better, you can get rid of just read messages by issuing
AT+CMGDA="DEL READ"
if you are operating in text mode, or
AT+CMGDA=1
if you are operating in PDU mode. I suspect the latter was the command you actually used to provide.