I read through the wp-testers discussion thread again and I've been doing my research before switching my permalink structure and frankly, I seem to find a lot of people using /%category%/%postname%/ as a custom option... this is not to say that it is wise, but it is fairly common.
In fact, several of the plugins I looked at that allow either multiple permalink structures (Advanced Permalinks, for one) or help you migrate links (Redirection, same author), even have features to use /%category%/ to start the link structure.
So this leads me to a few questions that I'm hoping someone can shed some light on:
If I change my entire structure to begin with the year or post ID, doesn't WordPress handle this with the proper redirect already?
If I change my entire structure to begin with the year or post ID, does the single database field in the wp_options table that holds all the current information shrink back down to a more manageable (read: faster) size?
Will this "shortcoming" be changed in a future version of WordPress that make my concerns irrelevant for now?
And finally, does using a plugin like WP Super Cache help with this issue?