The "Permanent link" link is a very nice feature which all power users like me adore, but it's hardly among the most important ones when navigating a wiki. Moreover, mw:Extension:Cite is bundled by default and adds a "Cite this page" link which uses plain language and provides a permanent link, so there is unwarranted duplication.
Aside from that, and more importantly, I believe we can find a home for this link that makes is less invasive while keeping it equally used and as easy to find for those who care for it: and I believe so because the permalink/permanent link feature is very common on the web, so we can copy some pervasive designs and users will immediately recognise them.
The easiest solution is probably to move the permalink to the timestamp in the footer, shown after "This page was last modified on". Most permalinks seem to use timestamps as link labels, nowadays. This was already proposed in 2005 at bug 3575; this design has become even more common since then.