The important thing to note here is that Google is not just competing with them now, they've commoditized the service altogether. This means that people are going to be less likely to ever want to pay for voicemail transcription.
We have a solution. You can bill them $3 a month for it, added onto their bill. They will pay it because they value their relationship with you (hah) and they don't want to have to change phone numbers just to save $3 a month.
We'll license our technology to you for a cut of that $3 plus a piddling few million a year. If you double the cut and guarantee a minimum of $STUPID_MONEY per year, we'll even agree to avoid licensing this technology to any other American cell provider, for as long as you maintain a growth rate of STUPID_RATE%."