[eluser]Chad Fulton[/eluser]
Damien:
I think you underestimate the power of page caching for non-logged-in users. (btw, Facebook most certainly caches its content quite aggressively)
Xeoncross:
I think this sounds like a good solution. Not sure how you're implementing it, but I have used the cache_override hook for this sort of thing, so if you haven't seen it, you might look into it.