VOIP / SIP gateway in New Zealand?

... pls help me get my head around this.

Business has a 12 month old NEC IPS 2000 PABX with voip capability (use
IP cards for trunk to trunk calling over frame relay to remote office
with same NEC PABX model, also use NEC softphones successfully).
GM now asking for us to set up the existing NEC IPS to utilise Voip
calls in addition to PSTN calls to overseas customers and suppliers as
a cheaper alternative.

So I figure we need these 3 things:

1. A decent internet feed - Tick, we have 5mbit Ethernet feed.
2. Some sort of hardware gateway to talk to a VOIP provider (where do I
start? Cisco?)
3. A VOIP provider that bills us for calls at less than the local
Telco.

Am I on the right track here?
Does such a VOIP provider exist down here in NZ? Could I use overseas
prov instead?
How do callers make VOIP calls back to you (e.g a staff member being
contactable at their desk phone via a Voip address just like using a
DDI?)
Phone system wise how would the NEC phone system determine routing of
calls via VOIP vs PSTN.

Sorry for all the questions, newbie to this. Want to get my head around
principles before going any further. Technology assumptions tend to
cost money :-)

.