Re: not DNS, but routing issues
You should have got a timeout error if you couldn't reach Plusnet's DNS cache, or SERVFAIL if Plusnet's DNS cache could not reach any of the authoritative servers for the domain you were querying.
NXDOMAIN means that the given domain name definitely does not exist (i.e. the authoritative server replied saying "no such domain")
dig is more trustworthy than nslookup for this; it shows the raw DNS request and response. And if you are running under Windows, I would not trust Windows' own caching. Nor would I trust the DNS proxies inside many consumer routers.
In such an event it is instructive to compare:
dig m.theregister.co.uk a # using your configured caches
dig @8.8.8.8 m.theregister.co.uk a # using a specific cache
Biting the hand that feeds IT
