It’s probably not advertised because it’s a niche feature.
On Telstra it’s still called MessageBank Plus, though, and it’s included on all Go Mobile Plans for post-paid Consumer customers. Business customers need to meet some minimum spend levels before getting MessageBank Plus for free; $55 for Go Business Mobile SIM plans, $60 for Go Business Mobile Casual plans, and $85 for Go Business Mobile SBO plans.
If you’re on an older plan with Telstra, such as the $80 Every Day Connect (with mobile phone plan) or $60 BYO plan then you also get MessageBank Plus for free, otherwise everything else is a $5 monthly charge. Note that MessageBank Plus is not available for pre-paid customers.
Here endeth my expertise, some Optus or Vodafone folks will have to chime in.
EDIT: Optus doesn’t look like they support visual voicemail, and Vodafone appears to have it included on every plan under the sun.