Based on my experience working with and for a few startups, it's likely that many of them did not. I've been asked by CEOs to not remove Company X logo even though there was no relationship beyond a customer account which used a Company X email address.

However, as several folks in this thread have noted, the process of working with customers' marketing departments is an opportunity to build relationships. Some won't let you, and that's fine. Companies like Apple often don't even let vendors who are core to their business use their name.