A startup with no money is not in business. Yes they have limited funding, and they have to use that funding wisely to build their product and customer base. But if you sell them a tool that will clearly help them to do those things, they will spend money. Heroku is the canonical example of this. They extract a premium price from many small startups who value a hassle-free production environment more than a few hundred dollars a month they could save by hosting themselves.

Do you think that Heroku makes most of its money from startups? I don't.

However they definitely do believe in getting people to be customers early. Hence they market to startups in the hope that they'll grow up.

I don't know about most of their money, but almost all of the companies listed on their (fairly extensive) success page are start-ups or small businesses.

To me, Heroku makes the most sense when you are building a business that may scale very quickly, and especially one that does not have a full-time sysadmin. It also makes sense for web apps that will stay very small and unlikely to grow that much past the free tier, but those are pretty much a loss-leader for Heroku.

If something is affordable and saves you money one way or another, it will sell even to early stage startups. Think Basecamp.