This patent crap is that, crap. And trust the telco guys to reinvent everything from the internet world in their attempt to catch up. Truly, idiots of the first order!
To implement visual voicemail, all you need is (a) a mechanism to inform a phone of a new message (b) an application on the phone that talks to a well known server and retrieves the message.
For (a), you can use SMS or any proprietary messaging. For (b), you can use a proprietary app and server. But, heck, you could even use imap so the phone's voice mailbox is syncronized with the server's with the messages passed as mime attachments. Just add a candy wrapper so it doesn't look like you are dealing with email. And imap would give you much more, such as the ability to forward messages from one voice mail box to other voice mail boxes or even, god forbid, email!
Its possible to set this up in under a week. All you need is a linux/bsd box with a telephony card, some code to digitize the audio and store it (asterix + sql will do), and an open source imap server. You can hack another open source email client written in java, python or whatever to be the phone client.
Notice, I said phone, not iphone.