[eluser]bretticus[/eluser]
Unless you can depend on some convention for your categories, there's really no way I can think of to pull this off with the existing CI base code. However, you could have a rule that checks to see if the first three chars are "cat-" and route them to your category controller. Then again, I'm wondering why a URL like category/search/birds would cramp your style
On a home-brewed MVC framework that I wrote recently (not CI) an SEO guy told me I had to stick geographic locations in my controller URI space. I accomplished this by tweaking my router class. That being said, you could always extend the CI Router.php class. If you do that, you can do what I did and use app caching to store the database categories in memory with a timeout (see APC or memcache.) I really hated the idea of smacking the database with a query every time for data that is fairly static.
EDIT: I stared answering and then walked away for a half hour so I didn't see Fuzzy's post. He makes a good point, there's nothing to stop you from using my app cache suggestion to dynamically build your route exceptions.