Visual Voicemail is a service that is closely integrated with the carrier's voicemail service. As far as we know, everyone with Mango (7712 or 7720) still does not have the final version, even if 7720 will end up being the final build number. It is considered "released to manufacturers" (RTM). They and the carriers still have to approve it, add in their bloatware (which is bearable with WP), and potentially build firmware updates to better utilize all of Mango's features.
People speak of Mango like it is our right to be using it already. I'm in no position to comment on the legal or moral aspect of this argument. But just keep in mind that the carriers haven't even released it yet. Even those people that have had Mango installed on their devices directly by Microsoft (I have two friends that fall into this category) have been told that not all of the kinks have been ironed out yet.
I am looking forward to upgrading to Mango just as much, or more, than the next guy, but I am content to wait for the official update to be rolled out, as excruciating as that is becoming.