Is it possible for the special:search logic to take us to [[category:foo]] if [[foo]] doesnt exist and [[category:foo]] does?
This should be an easy wiki extension to write, using the hook SpecialSearchGo(&$title, &$term). Just check for the existence of the article and the category, and modify the title correspondingly.
DanB