Vodafone doesn't provide VoIP, so you can't use them as your provider. I use both VFX from Xnet, and 2talk. There are a lot of recommendations for VFX on Geekzone. I've found it to be very reliable (using an old AG310 router). I've also found 2talk to be very reliable, although others have complained about 2talk's level of service. I'd recommend both. You can use VoIP on your vodafone broadband connection without any problems, assuming your line quality is good enough.
I suggest giving Xnet a call and buy one of their provisioned hardware systems. Dead simple and doesn't require much knowledge to set up at the consumer end.
Another thumbs up for VFX. you don't need to buy from VFX, but for ease of setup I'd recommend getting one of their supported hardware as after putting a URL into it and hitting save, that's pretty much all you need to do.
Linksys SP 2102 is what I chose - I have had one for 4 years now.
Not tried any other VOIP in NZ (I do use Skype as VOIP too) but other than the initial setup call to give them my MAC I haven't had to contact them. Never had any service issues.