P&S cameras certainly use the CCD without any specialized sensors (it only makes sense, since a DSLR simply cannot use the normal CCD while in viewfinder mode, so it has specialized sensors; on the other hand, some DSLRs that feature "live view" can't focus in this mode, as the software is only programmed to use the special sensors).
But the principle is the same in both cases: use a CCD (linear in DSLRs, two-dimensional in P&S's), and somehow assess contrast.
I do believe that Canon's focusing system only takes into account the viewport data (or, rather, the 2x magnified data), and not the full CCD array.
The algorithm you have described, based on Fourier transforms to determine frequency components, is almost certainly among the most robust; I'd prefer to implement something simpler, however, and it does seem feasible to measure standard deviation from a simple edge-detected version of the image (currently, a 1D derivative as I've said).
The problems I've experienced are more related to the part when you try to determine which direction you should focus. The method you have described (forget the threshold for a moment) seems reasonable, but what happens when 1) noise makes measured sharpness change in the wrong direction, or 2) the user focuses on a different subject (something pretty important for C-AF)?
So I should probably introduce some arbitrary threshold like you mentioned, although I don't like arbitrary threshold.
But then, anyway, the main problem becomes physically changing focus in arbitrary steps: simulated keypresses can't be used for that, and shooting_set_focus() crashes... :|