I haven't been able to update the old visual voicemail app (VVM) on my E4GT even though it's been telling me there is an update. I decided to side load an updated version (220.127.116.11) and it went fine. You'll then be able to do another update from within that new version to version 18.104.22.168. This will only work on Android 4.0 (ICS).
Here is the link: http://forum.xda-developers.com/showthread.php?t=1780975
Download the APK onto your phone and be sure you have the "install from unknown sources" checked in ICS or it may not install. ICS settings --> security. Be sure to uncheck that after the install. Not doing so is akin to rolling around naked in the mud; who knows what nasty buggers you'll pick up.