This is for Patrick Tisseghem, whose blog throws an "Out of Memory" exception when trying to leave comments, and with thanks to Nick who pointed me to the solution in the first place:
SPQuery, in it's default state will only query items in a given folder, by default the root of a list. This means that, without tweaking, SPQuery would be useless for most queries on DocumentLibraries, as these often contain folders.
But, have a look at Nick's comment to this post by Michael Hofer: Implementing SPSiteDataQuery - Learning by doing
It is perfectly possible to recurse folders by setting
query.ViewAttributes = "Scope=\"Recursive\"";
(Or if you also want to query the folder-type list items, use "RecursiveAll".)