They probably don't have to pay for any en/decoders distributed in New Zealand. If they want to distribute anywhere else they have to comply with that place's patent law (as well as all the other laws).
Is this true? Software patent is a gray area in the EU and I would not recommend to take for granted that European companies do not have to pay the h.264 license, even if they only distribute in Europe.
Concerning VLC, their FAQ [1] does not mention the EU aspect: they say that they cannot pay for the license because the software is free and that "the end-user becomes responsible for complying with the licensing and royalty requirements" (whether this would be defensible in court is debatable)
According to article L 611-10 of the French Intellectual Property Code, software patents are not allowed under French law. At the [EEA] level, Article 52 of the European Patent Convention has also excluded the protection of computer programs.
As a result, any software supplied by VideoLAN is not subject to licenses on any software patent, regardless of its origin.
The relevant section of the French IP law states that:
1. New inventions, in all fields of technology, involving an innovative approach with industrial application are patentable.
2. The following are not considered as inventions within the meaning of the first Section of this Article in particular: a) The discoveries of scientific theories as well as mathematical methods; b) Aesthetic creations; c) Intellectual plans, principles and methods in the areas of sport or economic activities, as well as computer programs; d) Presentation of information.
3. The provisions of Section 2 of this Article shall exclude the patentability of the elements listed in the said provisions only to the extent that the patent application or patent concerns only one of these elements considered as such.
4. Subject to the provisions of Articles L. 611-16 to L. 611-19, inventions relating to a product consisting wholly or partly of biological material, or to a process for producing, processing or using biological material, shall be patentable under the conditions laid down in Section 1. Biological material is considered to be material that contains genetic information and can reproduce itself or be reproduced in a biological system.
> the end-user becomes responsible for complying with the licensing and royalty requirements
Exactly. If you're using h.264 without a license in a country that requires it, it doesn't matter that some french people wrote the software for you. That's all they're saying.