Pages are not added to the History menu (nor the History collection in Bookmarks) during a browsing session. After quitting and reopening Safari, all items from the last session do show up in the menu. I suspect <http://trac.webkit.org/projects/webkit/changeset/24494> for obvious reasons.
Created attachment 15616 [details] Proposed patch
Comment on attachment 15616 [details] Proposed patch r=me
Fixed in r24511