Hi. I wrote the original question and I have to say that the FAQ entries are being searched, but not very well. I'm really not that impressed with DNN search in general, because even if the user found the FAQ they wanted, they would be directed to the page, not even the module nor the question they're interested in.
Anyway, before I roll up my sleeves and start debugging core modules like FAQ, I'd rather spend my time defining a nice UDT for my FAQs (with a nice XSL to display it) which does paging (FAQs do not) and can contain search. The AJAX stuff in the FAQ module is cute, but I think that it's anti-SEO anyway.
The UDT module is one of the most versatile, amazing modules I've seen. I built half of my latest site with it.. So my new question is, are you sure you want to use the FAQ module for FAQs? I am definitely not sure any longer.