Where they lived.
Because one of my cousins posted to FB: "Why do we still have phone books delivered? When was the last time you needed one?"
I told R. about this and speculated that within 10 years, even allowing for people who don't want them to go away, it was kind of hard to imagine paper phone books existing at all, beyond a few thin ones produced for highly local areas that continued to rely on a paper and wire-ful world. Then he said that Seattle got a punch of phone book producer pushback when they implemented an opt-out system (makes sense: they need to sell advertising, and advertisers don't want to advertise to all the people who didn't opt-out, right? Because that's just rubbing their noses in the obvious). He said 100K people signed up in the first few weeks, which is an interesting minority of the area's population.
Anyway, I latched onto the idea you could turn this stuff off. Here's one way:
Have fun! I'm all excited, because we not only opted out of everything (who knows if it will really work, but catalog choice's mailstop sure worked, so I'm feeling optimistic), we _threw away all the existing phone books_, mostly because neither of us could think of a scenario where we couldn't look a phone number up online but could somehow still have phone service.
ETA: In 2010/2011, Seattle and San Francisco passed ordinances which included penalties to phone book distributors who left books at addresses that didn't want them (I think Seattle had an opt-out and SF had an opt-in, but I'm not entirely certain). Last October, the 9th Circuit Court of Appeals overruled Seattle's ordinance on first amendment grounds: sure, phone books have commercial speech, but they have other speech as well and that gets full protection.
I analogize this to the right (and I do mean right) of Jehovah's Witnesses and others to litter our front doors with their religious paperwork. We may not like it, but it's sort of part of the current deal. And while you can rail against it, the odds of winning this particular battle are slim.
The good news is, the opt out page I mentioned above was created by the phone book industry in the wake of this kind of legislation, so Something Good Came of It All, I guess, altho not as effective an anti-littering operation as one might have hoped for.
ETA still more (live in fear -- there will likely be even more since I'm getting a lot of kid-related interruptions):
My sister is wildly skeptical that this will work -- she's called in the past and been told it goes to every door. R. points out that the people doing the delivery are paid by the ones they don't come back with, so they've historically dumped what they couldn't deliver (hundreds stacked outside a locked apartment building, type of thing) -- this is part of what motivated the Seattle ordinance, which he remembers being bandied about before we moved out in 2006. The comments at the above referenced link claim, as R. does, that the law requires that _all_ addresses receive a phone book, which is presumably from the days when phone books weren't delivered in economically less advantaged areas (and/or racially segregated areas, etc.).
Maybe we're going about this the wrong way. The catalog choice stuff is driven by the presumption that a catalog company has to pay to have the damn things printed and would just as soon not print and mail copies for people who are angered just to see them. Phone books, alas, have a perverse incentive: the publisher wants to keep the "subscriber"/delivery base high to justify a higher ad rate.
If we can convince enough businesses that advertising in the phone book is a pointless waste of time and/or get _them_ to lobby the phone book companies to stop delivery to people who don't want them (don't know how to accomplish _that_), the phone book publisher might actually listen.
Unfortunately, paper, ink and time on the printers gets cheaper and more available every single year that goes by, making production of these things tough to attack on a cost basis. Delivery is presumably done on a "contract" basis in much the way newspapers have historically been delivered. In an economic downturn, it's too easy to get reliable people to deliver the books, so pressure via labor is unlikely.
We may be stuck with these things for a while.
I guess the mediocre take away for me is, even if the opt out doesn't work, I took the step of throwing away the phone books, and will pre-emptively throw them away from now on.