I'm going to answer my own question, in case anyone else is trying to figure out the same problem. This all applies to Outlook 2007.
It is indeed an issue of categories not being supported in IMAP folders.
However, you CAN assign and display categories on a per-folder basis, at least locally. When displaying a particular folder, select View -> Current View -> Customize Current View. Click the Fields button in the resulting dbox. In the resulting Show Fields dbox, select Categories in the left list and hit the Add button to add it to the right list. I suggest moving it to the last position.
Assuming you started with the default set of fields, this will put the small customize box just to the left of the flag for each message summary. If you have a 2-line summary, the category name will probably fall onto the 3rd line where you won't see it (which is what I want, anyway). Right click on a customize box to set the category for the given message.
This customization will need to be done individually for every IMAP folder.
The category assignment will be persistent for a given message as long as the message remains in the same folder. If it is moved to a different IMAP folder, the categorization will be lost and will need to be manually reassigned. At least that's what I've seen.
Further discussion can be found in http://blogs.msdn.com/outlook/archive/2008/03/06/what-s-your-favorite-flag.aspx
Good luck.