I don't think VM's appear right away. You just have to trust that they're there for the other person to see. The exact same thing happened to me when I was holding a conversation, and not so coincidentally, it was the only time I made sure that he received it by going to his home page and pressing refresh. Then the duplicates came.
It's something that can be easily avoided if you just don't check to make sure the VM was sent. Trust that the server sent the message and all will be good. The only time I would make sure that the other person got the message is if it's been a couple days with no response and you've seen the other person online. Then politely ask them if they saw your previous message.