Has anyone tried http://swipehq.com? Their website looks good and the cost looks ok too.
(edit: Looks like fee is now $99, and there's a little more detail on their developers page.)
PX pricing is actually pretty good if you've got high transaction volume. But it's terrible for small biz. Most people I know default to Paypal.
Please Stripe, please come to NZ fast. You've been talking about it for more than a year. I know we must look like smaller-poorer Australia, but I promise there are people here who'd use you!