Happily it turns out that you can opt out here in Australia by ringing Sensis. I did this and while it's not one of the options they offer on the menu they did mark us to not receive printed books.
The call centre person obviously didn't get many opt out calls, it's pretty hard to find how to do it.
Personally I think printed books should be opt in and probably paid for.
The irony to me is all the environmental chatter on their site, saying that doing searches help save the environment. Surely the best thing they could do right now is to drastically slash the number of books printed by asking exactly who requires them. My guess is that it would be under 20% of the households.