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]
Comment on attachment 15616 [details]
Fixed in r24511