Speaking from a general DB design point of view, I think you have the right idea, but I would go about it in a different manner. Of course, I'm not a master of DB design, so I'm happy to be corrected.

What I would do is add a datetime stamp and a "node type" column (if the latter doesn't already exist). I would then create a separate table of node_types and what their maximum ages should be. Then, I'd run a cron that would delete any cache record that is older than the maximum age for its node type.

Alternatively, you could disable caching on User nodes altogether, and those viewing User nodes would just have to wait a bit -- but that's assuming User nodes are visited rarely enough that there wouldn't be a significant load savings in caching them over generating them on-the-fly.

Of course, all of this might be complete bunk because I haven't examined the PM code, and so don't know how it all internally works. But, generally, one would aim for predictable reduction in the best places rather than random reduction of oldest records.