Repost from two years ago because one of the mobile masters told me not to revive old posts. Still no Native Android Visual Voicemail, despite the fact that this was introduced in Android M.
Setup isn't even difficult for the carrier. Its a server side update and support for OMTP.
With Android 6.0 (Marshmallow) or newer now being on 48.2% of devices, I can't imagine why Koodo wouldn't provide this functionality for their customers.