I can't speak to the original poster's satisfaction with this, but this isn't helpful to me, and I have the same issue.
This is one of a very small number of bugs that, if fixed, would make Outlook fabulously more useful to me. As it is, it's really quite an impediment. Let me try to re-describe the problem slightly differently.
First, I have this problem both at work and at home. At work, this problem is compounded by a policy similar to the one Richard describes. We're allocated 250MB for a main mail file (can't even use the multi-gigabyte limit that Oultook would support) and the rest has to be archive files... so even recent stuff I really have to be on top of is already quickly moved to archive files. I have a lot of rules to try to sort out mail expeditiously from the main mail file into alternate mail files. (There are issues with having a lot of rules, which I've separately asked about.) But this means that one wants the same set of search folders for each of several mail files. So, let's build a hypothetical.
Let's say I work on Project A, Project B, and Project C. Let's say I have rules that auto-triage things into different bins. My "Favorite Folders" contains a list of things which include Search folders. They say things like "Unread Mail for Project A", "Unread Mail for Project B", "Unread Mail for Project C". This is already bad use of screen real estate because even on my nice big 1920x1200 screen, I don't have a lot of control of how big that display area is vertically before it runs into the other things I also want in view. So if I also want "To Do in Project A" and "To Do in Project B" and "To Do in Project C", I again get cluttered at three times the rate that I want to be. Then I might have "High Priority in Project A", "High Priority in Project B", etc.
And yet, Richard is again absolutely right that interactively I can search all the folders now. It's just that the search folders don't have a way to span. It's a bad loose end. Suggesting to use desktop search misses the point. Outlook offers me a feature that is a thing that is passively always visible telling me what's going on in my mail. I want that feature to be constantly in view in the way Outlook intends. I just don't want to see three times as many folders ... I want just one "Unread Mail in all folders" or "Unread Mail in selected folders", for example. Just one "To Do in all folders".
The problem with having these split up, too, is that I don't get an integrated ordering that shows me the highest priority or newest or whatever at once because I keep having to go back and forth between them. I need to see a merged view.
I hope that clarifies the incredible pain that it is to have these folders only be per-mail-file and how fabulously more useful and visually compact it would be if you could combine them.
I know you can't just wave a magic wand and make it different than it is, but if you could please feed back to your product design people that this is an issue, I'd really appreciate it.