The thing to remember is that search  results are security trimmed.
I'm doubting this is the entire problem, but search will only ever
return results that you have permissions to see. This automatically
limits the number of items  that search can actually return.

Have you checked your crawl logs to make sure there are no errors?

Maybe this will help:

insidesharepoint.blogspot.com/.../and-now-another-word-form-o
ur.html