Voicemail shouldn't be a carrier specific experience. Is there something so differentiated about the t-mobile voicemail experience vs. the verizon voice mail experience? Shouldn't there just bean android voice mail experience that the carrier can direct at their back end as appropriate?
I don't think it's unreasonable to expect that a core feature (like voice mail) should work out of the box with no additional installations on my part.