Voicemails are terrible. Anyone willing to sit through the message and talk to a machine rather than send you a text message probably doesn't have good news. Android M will make the whole process a little less painful with native visual voicemail. It's just a basic implementation in the preview, and it won't work on all carriers just yet. Still, pretty cool.
According to a ticket in the Android issue tracker, Google plans to include support for Orange in France right now and T-Mobile US in the final M release. Other carriers will come later, but it looks like T-Mobile voicemail is already working in the preview despite what the tracker says (see above via +Danny Hollis). I bet Fi will be supported too—it would only make sense. The M dialer has a tab for voicemail in M, which will show all available messages for playback and management.