Several players have reported to me problems with delivering in-game ("stored") messages. There do appear to be real issues in there with such messages occasionally getting lost without having been delivered.
I hope to straighten out the messaging system over the upcoming weekend, incidentally integrating the two disparate messaging systems and doing away with the whole email/stored message dichotomy.
In the meantime, I recommend everyone use the email relay instead of stored messages. Just click on the email link at the bottom of the Message panel in the client, which will send an email to the indicated recipient without revealing your own email address. You can also reply directly to any such email you receive; the RSW server will receive the reply and filter out your email address before redirecting it to the recipient.
Of course, you can always tell the other player your actual email address if you don't have any reason to keep your identity secret.
David