Nominet have done an astonishingly poor job of explaining why PO Boxes are not acceptable, but they are (almost certainly) correct.
From the reading up I've been doing, it appears that a PO Box, because it is not a "physical address" (it's basically a designation in a Royal Mail database that causes mail to be intercepted and forwarded, but it is not tied to "anywhere") is not an acceptable "address for service" under UK law. This isn't "because Nominet says so", it's "because the law of the land says so".
What Nominet are after is an address that IS a valid "address for service" so that if there is a need to serve legal documents (e.g. a DRS claim) they can send it to the address of record and thus fulfil their legal duty. PO Boxes don't meet that criterion.
I agree that it's a weird situation, but everything I've read suggests that the weirdness is not of Nominet's own doing i.e. the finger needs to be pointed at the inflexibility of UK law, not at Nominet.
If you would like to do your own research, I'd suggest Googling "address for service" "po box" and having a good rummage through the results that show up. There isn't one neat-and-tidy resource that explains the issue, but if you check enough results I expect you'll find that the above interpretation is accurate.