So I took try SIM card and put it in an Android phone and used the SIM manager app to try and delete the messages. But the app said there are no messages on the SIM card!
So now I'm completely stuck.
I have added some debugging to my Arduino code so I can see that the Re:Phone is sending text messages without a problem but not receiving them.
Maybe this is not a full SIM card problem after all?