Er, when I said 'more than once' I said 'more than once per translation unit', and this is almost universal. This reduces your claimed O(n^2) to, uh, O(nm) where n is the number of translation units and m is the number of headers.
Precompiled headers are useful in any project where you have one great big header that #includes a lot of stuff. This is extremely common.