It may be that targeted ads are more effective, but some counters to your points:
> John has a 10th wedding anniversary coming up.
A wedding anniversary is a significant thing–some John's may be swayed by an advertisement, but many would consider it a bit of a cheat not to put more "novel" thought into it.
> Mary is single and goes to the gym every day.
Frankly, the former of those two data-points could mean anything. Much of what advertisers believe about consumer habits of single people could easily be correlation.
As for the latter, anyone with a daily gym routine is less likely to want to change it. Selling gym membership to someone speculatively hoping to start going to the gym is a better bet, but much harder to track.
> Steve just got a promotion and likes the BMW 3 series.
Going back to the anniversary gift—I seriously doubt many people are much swayed by one-off ads in buying something as significant as a car (unless Steve has 10+ cars, in which case the promotion is less relevant). This is case where untargeted ads definitely have a much bigger role (Steve sees many BMW ads passively over a number of years).
It may be there's some cases were targeted ads are extremely effective, and some where they're not. And—as you've pointed out—it may be that Google et al. aren't really incentivised to actually be good at targeting as long as their advertisers believe they're good at targeting (which goes hand in hand with market dominance).