Screenshot of where the border is broken
After almost 2 hours of debugging I finally figured out what caused the tabs in Monobook to sometimes cause the border to be misaligned (see attachment).
For some reason the <a> inside the <li> was smaller than the <li>, which is odd since the size of the <li> is solely determined by its content.
More over, it displays right on mediawiki.org and beta.wmflabs.org, but broken on translatewiki.net and my local wiki.
The DOM (when inspected) looks completely the same, and no CSS styles applied differently.
Then I looked at the DOM and notice that on the "good" wikis, the output is:
<h2>Navigation menu</h2> <div id="p-cactions" class="portlet" role="navigation"> <h3>Views</h3> <div class="pBody"> <ul> <li id="ca-nstab-main" class="selected"><a href="/wiki/Sandbox" ..>Page</a></li> <li id="ca-talk"><a href="/wiki/Talk:Sandbox" ..>Discussion</a></li>
And on the "bad" wikis, the output is:
<h2>Navigation menu</h2> <div id="p-cactions" class="portlet" role="navigation"> <h3>Views</h3> <div class="pBody"> <ul> <li id=ca-nstab-main class=selected><a href="/wiki/Main_Page" ..>Page</a> <li id=ca-talk class=new><a href="/w/index.php?title=Talk:Main_Page&action=edit&redlink=1" ..>Discussion</a>
After ruling out Tidy, I narrowed it down to $wgWellFormedXml.
Or more precisely by Html::closeElement (called from SkinTemplate::makeListItem, called from SkinMonobook::cactions()), where it omits the closing tag of an <li>.
As a result, the browser only closes the <li> when it encounters the next opening tag, and as such includes a text node between </a> and (the implied) </li>.
This extra space causes the list item to be wider than the <a> it holds.