It can easily be resolved, charge the courier company the handling fee. If the courier passes that cost onto the customer, so be it.
That's exactly how they do it. No courier will pay it, so no courier gets to deliver to them. Congratulations, you just answered the thread.
As per my photograph on page 1 of a Fastway delivery to a PO Box, that has an NZ Post "Counter Ticket" applied to it, Google does not turn up anything even indicating that such tickets exist let alone what they are in regard to, but my guess is it's a ticket which means "this package is both accepted at and delivered at the same place and doesn't need to be carried further than from the counter to the back room" it probably costs some small amount, if that amount was charged to the sender I don't know.
If there was actually an edict "we will not permit other couriers to deliver to PO Boxes, no matter what", then I imagine that could be a bit dicey legally, anti-competitive and all that.
Counter tickets are associated with this service: https://www.nzpost.co.nz/personal/receiving-mail/counter-delivery. Essentially just providing tracking for parcels delivered to a counter delivery address so that Post doesn't get accused of losing it.