It depends on how they're doing it. Uber and Lyft, for example, are definitely startups under Blank's definition, because they were searching for a new model. Postmates too was new; I don't believe there was a successful delivery company that worked like they do.
If you were to start a Postmates competitor today, though, and were just doing what they did, then it wouldn't be a startup. At $250m ARR, their business model is already proven.
This would seem to exclude virtually all delivery service, cleaning service, car service, etc. companies, which are usually considered the prototypical SV startups.