How about, if you do what the message asks you to do? In other words, delete data to free up memory so that new messages can be received/stored.
Start by removing SIM messages using the Messaging app.
If that's not enough, start removing stuff from phone memory (e.g., move any and all photos/videos to a memory card, or copy them to a PC, or delete them if you don't want to keep them).
You can also uninstall applications that you are no longer using.