I'm on 2degrees, and if someone leaves me a voicemail, I never get an alert on my phone that I have a new text message (from 2degrees, informing me of the voicemail), despite being sent a message which appears in my inbox if I manually open the messages folder.

This happens on both an HTC Desire and an iPhone 4s, using the same number but different SIM cards and both pre and post pay.

Any ideas how I can be alerted to new voicemails? I'm missing messages because I forget to manually check after getting a missed call.