I had an issue where the Vodafone One Net voicemail notification sms messages were not showing up as new messages in my phone. I would get a new voicemail but not have a new sms notification on my phone, so unless I went into my messages app to see that the voicemail notification text was now top of the list but showing as ‘read’, I would have no other way of knowing that I had a new voicemail.
Turns out that when the notification sms is sent out, it doesn’t send a new message, but updates the existing message. The sms stays as ‘unread’ and therefore my phone doesn’t notify me of it in any way. I have an HTC One X and it’s also possible that it’s a phone issue rather than a sending issue.
However, to get around the issue, you can delete the message after receiving it. When the next voicemail is received a new sms will be sent and will show up on your phone as an unread message with appropriate notifications. Voilà.