Once again, despite my repeated attempts to halt delivery, the phone books turned up again.
In 2007 I formally opted out through Sensis's call centre and then again through their web site. The books came again in 2008. The so called "Green Office" program is a sham.
We never use the printed phone book. It will go - still wrapped - into the paper re-cycling again.
Update: It's 2011 and I'm pleased to report that instead of receiving a phone book I just received a card saying that they had received my request not to get it.
They go on to say that my request will be honoured for three years and then they'll revert to delivering books again unless I let them know again.
So, good on you Sensis at last.