Here in the UK, I've used voicemail with:

Nokia 6210 on Orange contract
Nokia 6120 Classic on 3 contract
Sony-Ericsson K850i on 3 contract
Nokia 2630 on Vodafone PAYG
Nokia 2630 (after unlocking) on 3 contract
Nokia N900 on Vodafone PAYG

Out of all of the combinations, I've only seen a voicemail icon on the ancient Nokia 6210 on Orange. All the others sent a text.

So I wouldn't call the voicemail icon a common, basic feature that other phones/networks have. Clearly they don't.

I have read that the "voicemail flag" is an operator dependent feature.

Frankly an icon or a text are both annoying. In this day and age we should be receiving "voice messages" in our inbox, alongside emails and texts. Virtually all phones can receive them.

The fact we don't is ongoing proof that network operators still hate their customers, and a reason to cheer on Google Voice, if only to force network operators to grow up.