The Australian telecom Telstra announced yesterday that Bruce Akhurst, CEO of its Sensis directories unit, has resigned. Akhurst had once been seen as a rising start at Telstra, but his failure to complete the transformation of Sensis from a traditional to a digital media company likely secured his fate. In fairness to Akhurst, his struggles are shared across the global Yellow Pages industry.

Akhurst’s departure comes in the wake of the Sensis’ steady erosion. In the most recently completed half year (ended Dec. 31, 2011), the company saw its revenues fall by 24 percent.

Rick Ellis’ recent arrival at Telstra was likely the first signal that Akhurst was on notice. Telstra CEO David Thodey effectively demoted Akhurst by placing the Sensis business within Ellis’ portfolio. Ellis comes to Telstra from Television New Zealand, where he was CEO.

As Group Managing Director, Digital Media, Ellis will oversee Sensis as well as all of Telstra’s digital media efforts. In addition to Sensis, Telstra owns a 50 percent share in the Australian pay TV company Foxtel. One of Ellis’ major priorities will be Telstra’s plan to invest in a high-quality video streaming platform. Once Akhurst leaves, Ellis will run Sensis on an interim basis while a search is under way for a permanent CEO.

Akhurst has been at Telstra for 15 years, the past seven at the Sensis helm. His tenure at Sensis has been full of highs and lows. He is perhaps best known for bringing in a group of U.S. based Yellow Pages executives led by sales veteran Carol Johnson and committing to a strategy built around growing print revenues. This effort was based on the premise that print had sufficient untapped value to drive growth. The company focused on improved execution and more proof of value in print, and for a time the strategy worked. As late as 2009, the company was still generating print growth. Johnson joined Sensis as COO in 2007 and left in 2009.

The print-centric strategy was ultimately unsustainable,with print turning south in the 2010 financial year. Last year Sensis rolled out a new strategy focused on becoming a digital solutions provider to SMBs. Rapid erosion in its biggest markets, Sydney and Melbourne, has been at the root of Sensis’s recent decline.