However there are many servers set up in NZ where the forward and
reverse DNS do not match, or there are no PTR records at all. After all
this is outlined in RFC 1912 (section 2.1) and RFC 1033

These are both informational RFCs, so there's no requirement to implement what they say (as nice as it would be...)

I am being too hopeful to expect mailservers to be configured
correctly? I'm stuck between wanting to do things properly and help
reduce SPAM on one side, and having customers on the other saying why
can't I get mail from XXX.

iiNet made the change to blocking all servers without reverse DNS some time ago (they don't enforce that it must match forward - just that it exists). It caused some paid, but not a huge amount. The forums on whirlpool.net.au will give some idea of the problems they had.

I'm not sure how much it actually bought them - to a large extent you're just blocking what RBL's/reputation services would have stopped in the first place anyway.

Enforcing forward/reverse has at least one fairly major downfall - if someone ever tries to change the name of a server/IP address, the different caching/propagation between the forward and reverse names will most likely mean that you'll end up blocking mail from them for a period of time. This happened about 6 months ago for a major ISP somewhere (unfortunately I can't remember exactly who). Yes, there are ways to do this right, but are you going to trust every ISP/corporate admin to get it right?

Scott.