When you say "@foo Hi, foo!" You're sending a message to some person named foo. That's a push. If you start thinking of it as a pull, then you get in to the sort of trouble you're mired in.
In a distributed system the process goes like this:
1) Sender queries name server: WHOIS foo? 2) Nameserver responds foo is http://www.foo.com/mytwitterfeed. 3) Sender pings recipient http//www.foo.com/mytwitterfeed?ping=messageid&origin=bar 4) Recipient queries name server: WHOIS bar? 5) Name server responds http://bar.com/mytwitterfeed 6) Recipient requests message text, http://bar.com/mytwitterfeed?id=messageid and verifies it actually is addressed to him.
From then on, you have to worry about spam but that's a solved problem (killfiles, Bayesian filtering, etc.) No caching is involved. Recipients store messages addressed to them, just like any other messaging system. This isn't at all a hard problem.