I never really grokked the behavior until now. It seemed like only a subset of my search folders that I created while I was in cached mode were communicated to the server. This meant that whenever I set up a new Outlook client install, not all of my search folders (that I had set up on another machine) would show up automatically.
Furthermore, once you have more than one Outlook install pointed at the same account, their search folders list gets out of sync. Not useful when you’re trying to maintain a big list of folders for reading mailing lists.
Well the trick seems to be to do something to cause your client to upload its search folder list to the server. One thing that seems to work for me is to edit the server side Rules list. Even just changing the name of a rule seems to work. Once I do that, it seems like any locally created search folder gets communicated to the server, and after a little delay, my other Outlook clients will pick it up.
I wish they could just sync it when I create a new folder. Oh well.