Just saw this announced on twitter:
http://www.telstraclear.co.nz/residential/homeplan/internet/naked-broadband.cfm
From what I can gather it only works in UCLL areas (it didn't like any addresses I gave it unless it was close to an exchange)
Looks like you can get a phoneline with it but unsure if they mean VoIP ?