Nothing wrong with the software, the message was deleted before you received it. If you send somebody a PM, it goes into your outbox until they look at it. You can still go in and delete it until they view it. Once they view it, it goes into your sentbox and deleting it will do no good to 'unsend' the message.
Was this clear as mud?