Well what happens typically is people stop going for the low hanging fruit, and focus on specific verticals. When the best and brightest devs are working on specific areas they love then everyone wins.
When they're gap filling, then their best hope is acquisition, no matter how much they love their product. And remember acquisitions aren't guaranteed, and there are only ever one or two of them.
"Search" is not a vertical market. It's something ALL of Google's customers use (or would use, in your hypothetical). I guess I do agree with Des on that main point. Plugging a gap in someone else's software may not be a great long term strategy.
Search alone isn't vertical, search alone isn't even a market if people don't pay for it. You misunderstand the (Google) business and who the customers are. Those doing the searches are not the customers. Advertisers are the customers. Eyeballs of those searching are the primary product. Search isn't the product, only part of the means to obtain the product. Search is a supporting part of a vertical structure that produces revenue for Google.
It's the same thing with commercial broadcast television. The viewers are not customers, the programs are not the product.
In both cases, the choices that produce maximum advertising revenue are not necessarily those that deliver what the person searching or viewing considers best.
In the case of Google, there are elements of a vertical market in the sense that they're combining pieces. They just aren't combining the same pieces or using them the same way as most others. They don't actually sell a mobile OS, or (with past exceptions for developers) handsets. I don't believe they're directly producing much video either.
And while they mine data, that is yet another companion component to drive sales of or increase value of the advertising. The will tell how apps fit into their revenue model. They relate to attracting users, more ads in some cases, and a cut of sales. Even if not a big part of the total phone revenue stream, apps are still something that they're stuck dealing with.
There was search before Google, there was data mining before Google, there were ad brokers before google. They're well beyond all of that, more vertical than any of those things alone. In some cases they're filling in gaps or providing alternatives in other vertical products (handset/OS/carrier) only to insert their ad business into the equation. Mapping, video hosting and other things they do also are methods to increase the value of ad business, or build pathways to insert themselves into other ad funded businesses (perhaps broadcasting)
Whether a particular model or product is "good" all depends on perspective. A model where the OS is nearly free appeals to some handset makers or carriers. Low budget "reality" tv and infotainment news programs with 18+ minute of ads an hour may appeal to a tv network if it has a better viewer/cost ratio than obtained with more expensive quality programming.
So what's the difference between a vertical and "gap-filling"?
If Google didn't have product search, or blog search, and someone went and did that, would they be gap-filling or going after a vertical? Seems to me they're one and the same.
The OP quoted Spolsky mentioning “a feature... for dentists”. That’s one example of a vertical market.
My last employer made a search engine specialized for geography: government agencies and energy companies (two other vertical markets) paid beaucoup bucks for it. (Not beaucoup enough to satisfy the VCs, alas, but the product itself is still being sold by another company.)
