It seems to me that perhaps we are thinking a bit too aggressively on page caching. We're trying to cache the entire page, which makes things unworkable for users with special preferences.
Instead, perhaps we could do a partially cached page with escape sequences for areas that need special parsing because of preferences. For example, things like '''bolding''', preformatted text, external links, etc - those are unaffected by preferences, and so can be completely cached as HTML. Now, for things like links, the scanner can change the code to a set sequence - for example:
[[Rabbit]]
Would be changed to: <% make_link("Rabbit", 1) %> (or whatever the function is) - so, it just looks up the user preference, and executes that function (with the one indicating that it is an active link).
Or, it could be: %%%%IHref|Rabbit|1%%%% - where the scanner searches for the special token (in this case, %%%%), and looks up what to do based on the first section of it (IHref - internal link, Rabbit - name of link, 1 - active link).
This way, we could have three scanners, each of slightly different speed and functionality:
1) Fully cached scanner for anonymous users (which basically just shoots out the fully cached page)
2) Partially cached scanner for logged in users (which only has to scan for the escape sequence and then act in the appropriate manner based on user preference)
3) Full scanner - which produces both cached pages, in addition to sending output to user.
If we do it this way, and cached user preferences, we could avoid having to access the database at all in the case of 1 and 2.
Does this seem like it could work?