I have been doing a bit of work recently with the SPSiteData Query in SharePoint. Dealing with CAML with this isn't the easiest especially when it only returns a subset of information that it should from a site.

As I was developing my queries I was using the fantastic U2u CAML Query Builder and getting my queries to work perfectly. What became really annoying is that they didnt work in my custom web parts. After many hours of banging my head against the wall, I found a KB Article

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

Reading this title I thought WOW and then realised that the update was fined in the Infrastructure Update, I am running SP2. After bashing my head against the wall a few times, I realised that the way I installed SharePoint was with SP@ slipstream media. After an uninstall of SharePoint and then a SP1 install followed by a Infrastructure update install and finally SP2 install the queries started to work

If you're having trouble with your queries that should be working then make sure that you installed the infrastructure update before SP2