The following code inserts a link for extended search into the headers top link navigation

<reference name="top.links">
    <action method="addLink">
        <label>Advanced Search</label>
        <url>catalogsearch/advanced</url>
        <title>Advanced Search</title>
        <prepare>false</prepare>
        <urlParams></urlParams>
        <position>6</position>
    </action>
</reference>

It is really important, that all sub elements of  the action tag are in the exact this order as the corresponding parameters of the underlaying method Mage_Page_Block_Template_Links:: addlink.

If storecodes are used, you have to set the prepare node to true or 1. It generates correct URLs!