1: The major reason for voicemail and related services (slamdown notifications where you get a text message stating that someone called you but didn't leave a message) are NOT the minutes you spend but rather call completion. You see, calls that don't terminate when your terminal is not online (a not uncommon occurance in crap networks like the US ones, you would not believe how much time a normal handset in a metropolitan area is offline) are a loss since you don't get missed call information. There is a very, VERY well understod business case for voicemail services and how they affect the average revenue per user.
2: What customers SHOULD do is require that all operators allow them to connect to Google Voice type services, i.e. a service provider that will let them govern the way they receive information and control the modus in which they respond themselves.
3: The charging model of US operators is completely insane compared to the rest of the world. How the hell can you put up with it? Seriously?