Is there a macro/add-in/hidden function in Outlook that can keep you from creating uncategorized tasks, contacts, etc.? A VBA script that brings up a dialog box saying "categorize me!" when you attempt to close the window and save the record without adding a category to the item seems like it would be trivial to code (if I knew anything about VBA).
Or preferably: after you try to save something uncategorized, the macro automatically displays a pick list of categories, and saves the record once at least one category has been chosen for it? It seems like it would be easy to implement, and it surprises me that there's nothing readily available in Outlook to do this (or if there is, it surprises me how well they've hidden it!).