How can you force SPQuery to return results from all the folders of the list?

By setting scope of ViewAttributes to RecursiveAll

If you want to get results from all the folders in the list.. then you need to specify the scope of the query by the use of ViewAttributes. e.g. query.ViewAttributes = "Scope=\"Recursive\"";