Good job upgrading and sharing this. I can't wait to try it out in production.
Idea: When the original query took less than x microseconds don't cache it anymore.
The two biggest delays in retrieving past query results from the cache is (A) the filesystem and (B) the expeditious unserialize() function.
The combined delay of these two is measurable, and either a lower limit can be benchmarked during plugin activation, or a lower limit can be hard-coded in the plugin. The byte size of the query results could be considered, of course.
It makes no sense caching a query if running the original query is faster than retrieving a cached result.
Hopefully this will eliminate many tiny cache files. Fewer cache files = faster cleanup. What do you think?
See also http://wordpress.org/support/topic/252983?replies=3#post-1196721 and the one-line hack in http://wordpress.org/support/topic/234465?replies=13#post-1196851 for other ideas.