As well as PAF and the NLPG, there's also the CTVL (Council Tax Valuation List), which has a lookup facility buried on the VOA's site:
Another example of the ludicrousness of PAF is that they can't agree on where to put flat numbers. The gazetteer I use at work (part of OLM's CareFirst) used to be populated by PAF (before we realised it was easier and cheaper to do ad hoc 'net lookups), and quite often flat numbers would be located in the Building field (where 'A' and 'B' numbers are also stored), which makes updating the list of flats in a complex a complete PITA. Far better to just manually create the building containing the flats, then allow the social workers to put in the flat name / number as required.
PAF is also completely hopeless at caravan parks and narrowboats, not to mention being painfully slow to update. CTVL tends to be quicker (why aren't I surprised?) but isn't perfect, and we don't have access to the NLPG.
Oh, and if you're doing postcode / address lookups on the Royal Mail site, it's stupid enough to use a cookie to determine how many lookups you've done. Navigate away from the site, clear the cookie, and you've got another 6 lookups (not 15 as they claim - once you've used 6 you have to sign up or log in). Their CrAPTCHA is one of the simpler ones out there, but still makes distinguishing C and G hard (0 and O are also almost indistinguishable, but their CrAPTCHA is always three letters followed by three numbers, so you can work out which it's supposed to be.)