Sage103082: I had this issue with a pm I sent yesterday. I typed a pm up yesterday afternoon and it looked to have sent fine. Last night I checked my message and the PM was gone.
Grargar: I've had this happen quite a few times, especially when writing a long PM. My solution to this is simple; write your message, copy it, send it and then refresh. If your PM is not available, paste it, send it again, refresh and now it should be available. Normally, it shouldn't take more than one retry, but you never know.
^This 100%. I always hit refresh after every PM to enure its delivery. But the copy/paste has saved my bacon a number of times ;-)