All the money comes from some of the users. Sure Google is collecting everyone's data, but in the end the vast majority of it is worthless. I'd be surprised if even 1% of users are profitable for the ecosystem. The tiny minority clicking on ads and buying products is subsidizing everyone else.
So I have to recoup that cost. I pass that cost onto all of my customers by mixing it into the cost of goods and services. If you buy things from me, even if you are not a subscriber to google/yahoo, you have in effect paid for those services. This is somewhat invisible to the people with those email addresses but does actually affect them, if only a little bit.
Google would tell you that you can simply start with a low volume and ramp up slowly. In reality this is simply not practical for most businesses. This gets into discussions around queue-per-domain management and rate-limit-per-domain, but quickly falls apart when you have to notify a large number of your customers on a time sensitive transaction that is out-of-band from their web browsing experience. A modern work around is to have a cell phone application for notifications rather than email assuming you let your own customers choose that over smtp in their profile. Another work around is to use an email campaign provider that already pays into the whitelists, but then I have to give your email address to a potentially shady company that may cross-sell / cross-market to you.
The user pays for Google in the end, just not consensually. It's a closed loop. All the money ultimately comes from the users. Product or politics, all advertisers are expecting to get some return.
Unfortunately it's in human nature to not want to pay. Search needs to be a utility that we all fund to make it the best tool for society.