There's a word for that: a business.

If someone built a bar in your neighborhood, would you call it a startup? It meets all your criteria. But at that point the word becomes useless.

You could argue that it's not a new service. Yet some of the most successful startups applied technology to old ideas, like Craigslist and eBay.