I had a similar issue with my faulty(as in locking up) 64GB N9, what was causing my problem was smileys, if my wife for instance sent me a message from her iphone containing smileys then I simply wouldn't receive the message. If there were no smileys in the message then I would recieve it no problems.

I didn't have the phone long enough to say if the issue extended to other phones as had to send it back sadly, might be something to look into though.