Obviously specifics make a huge difference here so it's hard to generalize, but generally, finding the market is not a new problem. In the current business environment, the entire ecosystem is rigged against you, forcing you to advertise. Consumers are so inundated with advertising that almost have no energy leftover, or any expectation that they need to go out and search. Worse, search is distorted in all the wrong ways because of the exact same incentives. Your competitors (or even poorly-fitting tangentially-related products) are stealing discovery from you by capturing searches through advertising. They can't even get to you because a wall of SEO stands between them and you.
I think I (mostly) agree with you, but it seems like SEO and search in general would be even more distorted if outright advertising were disallowed or penalized.