I use the CMGD command to delete messages.
As far as I can see the CMGR command is used to read messages and not delete them.
Edit (since you were using the CMGD command)
It is possible that your modem doesn't support multiple parameters to the CMGD command - my Siemens modem does not (or if it does it doesn't list it in the AT command set document). Instead of deleting all the messages in a single command I do a CMGL to get read messages, parse the results to get the index and them delete them one at a time using CMGD. If you do find another way I'd be interested.
Use the AT+CMGD=? command to find valid values of the parameters.
Edit (since you verified the modem supports CMGD with two parameters
I don't know what the problem is.
I did notice that your CPMS command gives different results to mine, example of mine:
AT+CPMS?
+CPMS: "SM",10,10,"MT",12,35,"MT",12,35
Yours doesn't have any storage memory string. I'm guessing the command you actually did was:
AT+CPMS="ME"
When you switch to ME storage and do a CMGL command does it list the undeleted messages?