The GetSiteData method in SharePoint allows querying list items across multiple lists and webs. It is extremely useful because it allows for recursion and searching across the entire Site Collection. It uses CAML syntax and returns a DataTable.
Unfortunately it also contains a known bug in some SharePoint versions, preventing it from returning all existing results for a given query.
The problem is only visible in some situations, for example, when searching in more than 10 document libraries, so it might not affect everyone.
The GetSiteData method is also used by SharePoint, for example, in the Content Query Web Part (CQWP). If you're not seeing all expected results from your CQWP, then it might be because of this.
Microsoft has a KB article with more detailed information about this issue: Search results are incomplete when you use a CAML query that uses the SPSiteDataQuery class to search content on a SharePoint Server site or on a Windows SharePoint Services 3.0 site.
Microsoft offers a fix for this in the SharePoint Infrastructure Update of July 15, 2008 (KB951695 for WSS3 and KB951297 for MOSS). This upgrade brings your SharePoint version to 126.96.36.19918, so if you have an higher version, you already have it.
However, there have been reports by some people that this doesn't completely fix the issue. You should install it if you're having this problem, though. If it doesn't work you can try dividing your results in multiple queries.