I'm wrong about the PublicTimeline. It is cached (just not the same place as a user's Timeline). And it is updated in real-time, too. Both timelines use Message.findMessages, which uses a LRU.
There are places where checking the permissions via the access pools could be optimized, but doesn't seem related to the boom of String message objects.
