To be honest, I've seen this problem here and there and tried to address it in various ways, but I never really could reproduce it or strike gold on an across-the-board fix. If you hit on something, please let us know... somehow blocks do get cached along with the whole page for anonymous users, but it just doesn't seem to happen to everyone.