One of the websites I work on has been having this problem on frequent occasions. Their problem is that some future-dated posts do not get published once their time comes around, and on a couple of rare occasions they have had a future-dated post getting published months early!
My searching has led me to the scheduler within WordPress. As far as I can tell future-dated posts get an entry within the scheduler which will publish the post (via publish_future_post) once the time comes around. However, the posts we have problems with aren’t listed in the scheduler. Choco-cookies forcing a database upgrade seems to work because afaik it re-creates the entire schedule from a raw database request of all future posts.
There must be a bug, caused by (so far) unknown conditions that causes a future-dated post to be removed from the scheduler and thus never get published.
