I use CMake everyday and for me it's not a database but a set of modules. Each of this module will look for a particular thing. Some modules are better written than other but they all allow you to bypass them. Of course on obscure systems it will fail. That's why they are called obscure. But on systems following more or less the good practice, there will be no problem at all. On the others, you need to pass the specific path, but it will be true with autoconf too... no magic here...
Also in the doc, it is stated that if you rely on a specific flag/option/function then you need to test for it, and CMake gives you the tool to do it. That's a good practice everyone should follow.
But I agree, it's not always done. Like Autoconf, I guess it really depends on how well the developer understand the tool, and how much time he is ready to spend on it.
There's no magic, it's a complicated problem, with only complicated solutions. CMake is more attractive to me, because it allows me to do simple stuff easily, but more complicated operations are also possible.