Dentistry's an odd one. In some parts of the country it certainly used to be essentially impossible to get an NHS dentist, and in others it's easy. There are multiple dental surgeries accepting new NHS patients in Oxford, for example, which is by no means a cheap place to operate.
Although NHS dental treatment isn't generally free for adults, it is pretty cheap. I've been lucky enough to find an NHS surgery everywhere I've lived and the standard of care has been generally excellent.