At Norwegian (bokmål) Wikipedia there is a few experiments on portlets with adaptible menu entries as gadgets. The idea is to adapt the entries to the users actual needs, and not attempting to find some small common denominator for all users. After a couple of iterations it was pretty clear that the present organization of the sidebar was not optimal.
A page is part of some context. Either it is linked to from a page, it is part of a category, or it is within a namespace. After several iterations it seems like the best approach is to use the namespaces as context. This will map navigation to portal, project to wikipedia (which also has an alias project), and so forth. A portlet help would be added too.
There would also be some more specialized portals like the language box, but that would act a little bit different and is better dropped in this discussion.
When the user visits a page it will be added to one of several maintained lists of pages, each list follows one context. Initially the page is just added to the front of the list, with a page visit of one, and as more items are added the older items propagates down the list. Finally they reach the end of the list, or rather the array has reached its maximum length, and they drops off. If a page is revisited before it reaches the end of the list it is removed from the current position and reattached to the front of the list and the visit counter is incremented by one.
The handling of the list as such is a least recently used algorithm, the oldest entries are discarded.
When the the portlet menu for a specific context is built the present visits page list is sorted and the highest ranking items that are not already listed in the portlet are added.
The construction of the menu from the list is a most frequently used algorithm (see also least frequently used), the most frequently used entries from the list are used for the menu and the other ones are "discarded".
Initially there should be a base set of items. This will be used if there are no other known entries that should be added to the list. Typically this would be used for any anonymous users, and it will also be used for logged in users when there are no previous known page history for the given context. These entries will be overridden by the user as he visits pages.
Some pages would also be of so much interest to the user that he want to pin the entries in the portlet. This is not the same as a watched page although it is very similar. The algorithm as such is not dependant on how this is done, but it seems that either drag and drop (dragged from the lower part of the portlet to a higher part) or a clickable item attached to the menu entry is the most obvious way to set something as pinned in the portlet.
A special case exist when the user visits an non-existing page. If this happens the page will be removed from the list of tracked pages.
It seems like there should be a navigational page for for each portlet, and probably this should be reachable from the title of the portlet. This interferes with collapsing/expanding the portlet in Vector, but perhaps the arrow part is sufficient clickable area.
The lists will quickly grow and become a little to large for storage in the servers, although compared to the watchlist it isn't that large so it could be possible to save it as is. Still it might be more interesting to maintain a full list client side, and just keep a subset at the server.
If the user is anonymous then the server will not log visited pages. In this case the logging will only happen client side and different browsers will possibly get different winning entries. It is possible to argue that an anonymous user should only use session storage for these lists.
A variation for logged in users is to maintain a last updated timestamp, and push the top of the list from the client and to the server when the session is initiated if the client has a newer list. If the server has the newest list the client pulls the top of the list from the server. Afterwards the client lazy-updates the server. This strategy relies on local storage to maintain persistent state in the client browser.
A similar technique can be used for the language links, but note that in this case it is not the pages themselves that are being logged but the language markers. To facilitate this an event handler is attached to the links and session storage is updated just before the client browser fetches the page. It can be argued that this only has an effective implementation with use of local storage.
It is worth noting that the visited lists are a very potent fingerprint for the user. If a user has several pseudonyms then the lists should be kept separate to avoid detection both by someone that has access to the server and someone eavesdropping on the line.