This is a very old post and a really old version of the CMS, I know, but the issue was most likely that the scheduled publish does not fire off the publish event and then the cache is not invalidated (since the cache invalidation is done on the publish event). This is true for later versions as well, that´s why I answered this question.
I wonder is there is any known-bug for this issue, could not find anything on the matter.
This is what happens:
Sometimes after editing a page, marking it as ready to publish and scheduling it for publishing. It gets published but the cache is not updated in the other servers. This happens sometimes, I tried to find a pattern or the reason for why it sometimes works and sometimes not. Any help or advice is appreciated.