Ive shipped two 16"x20", framed (with glass!) prints to New Zealand via USPS Express International. They both arrived in perfect condition, and several days earlier than the delivery estimate.
The shipping boxes were begged from a local furniture store, and were originally created for shipping mirrors. I would have preferred to ship without glass, but the buyers requested it.
I know one artist who recently shipped a large (36x36x6), stretched painting to Australia via USPS Global Express Guaranteed. Her shipment arrived early and undamaged.
USPS offered the best prices I could find, and did a great job. I'd happily ship to NZ again, or to Australia.