Well MMS do require data to download them. But what has voicemail got to do with MMS? Does your carrier have some setup where it sends voicemail messages as MMS? That is unusual.
I've known phones that hide the fact that MMS uses a data connection (basically turning on data temporarily to download). Can't say how common that is because I very rarely receive MMS (i.e. I've received 1 in total in the 6 months I've had my current phone, and that's an unusually high number - I don't know anyone who still uses them really). But yes, many, maybe most, require you to explicitly turn data on to receive MMS. So if your voicemail uses MMS I can believe that you need a data connection.
And of course iPhones often handle voicemail their own way (the "visual voicemail" feature, if the carrier supports it).