I believe the missing "keys" are the following two items:
<action method="setDefaultDirection"><string>desc</string></action>
<action method="setDefaultOrder"><string>relevance</string></action>
You should be able to acomplish this a couple different ways... in either case you'll need to make local copies of the said files.
1) If you don't already have one, add a local copy of 'catalogsearch.xml'
Note:
Since Magento layouts work "cascading" it's a good idea to first check any "other" Magento layout directories available (other than the 'base'). For example, in my case we use EE, so we check the 'enterprise' layout directory first to copy files before looking in the 'base' directory.
Common locations of 'catalogsearch.xml':
/app/design/frontend/base/default/layout/catalogsearch.xml (as last resort)
/app/design/frontend/enterprise/default/layout/catalogsearch.xml (for EE)
Note: There may be a different location with PE as well... I'm not 100%.
2) Add the following within the 'catalogsearch_result_index' section in 'catalogsearch.xml':
<action method="setDefaultDirection"><string>desc</string></action>
<action method="setDefaultOrder"><string>relevance</string></action>
For example:
Referencing the 'search_result_list' handle (ie enterprise layout):
<reference name="search_result_list">
<action method="setDefaultDirection"><string>desc</string></action>
<action method="setDefaultOrder"><string>relevance</string></action>
</reference>
So it would end up looking similar to:
<catalogsearch_result_index>
...other code
<reference name="search_result_list">
<action method="setDefaultDirection"><string>desc</string></action>
<action method="setDefaultOrder"><string>relevance</string></action>
</reference>
...other code
</catalogsearch_result_index>
Or you can place directly within the 'search_result_list' block (ie base layout):
<catalogsearch_result_index translate="label">
<label>Quick Search Form</label>
<reference name="root">
<action method="setTemplate"><template>page/3columns.phtml</template></action>
</reference>
<reference name="left">
<block type="catalogsearch/layer" name="catalogsearch.leftnav" after="currency" template="catalog/layer/view.phtml"/>
</reference>
<reference name="content">
<block type="catalogsearch/result" name="search.result" template="catalogsearch/result.phtml">
<block type="catalog/product_list" name="search_result_list" template="catalog/product/list.phtml">
<action method="setDefaultDirection"><string>desc</string></action>
<action method="setDefaultOrder"><string>relevance</string></action>
<block type="catalog/product_list_toolbar" name="product_list_toolbar" template="catalog/product/list/toolbar.phtml">
<block type="page/html_pager" name="product_list_toolbar_pager"/>
</block>
<action method="addColumnCountLayoutDepend"><layout>empty</layout><count>6</count></action>
<action method="addColumnCountLayoutDepend"><layout>one_column</layout><count>5</count></action>
<action method="addColumnCountLayoutDepend"><layout>two_columns_left</layout><count>4</count></action>
<action method="addColumnCountLayoutDepend"><layout>two_columns_right</layout><count>4</count></action>
<action method="addColumnCountLayoutDepend"><layout>three_columns</layout><count>3</count></action>
<action method="setToolbarBlockName"><name>product_list_toolbar</name></action>
</block>
<action method="setListOrders"/>
<action method="setListModes"/>
<action method="setListCollection"/>
</block>
</reference>
</catalogsearch_result_index>
3) Make sure to dump the Magento cache/storage and reindex.
The other option would be to place them as 'hidden' form elements in 'form.mini.phtml'
1) Place the following within the form in 'form.mini.phtml':
<input type="hidden" name="order" value="relevance">
<input type="hidden" name="dir" value="desc">
Now, the beginning of the form in 'form.mini.phtml' would look similar to:
<form id="search_mini_form" action="<?php echo $this->helper('catalogsearch')->getResultUrl() ?>" method="get">
<input type="hidden" name="order" value="relevance">
<input type="hidden" name="dir" value="desc">
...other code
2) Change the path to 'form.mini.phtml' template within the 'default' section ('header' reference handle) in 'catalogsearch.xml':
<default>
<reference name="header">
<block type="core/template" name="top.search" as="topSearch" template="custom_template/catalogsearch/form.mini.phtml"/>
</reference>
... other code
3) Make sure to dump the Magento cache/storage and reindex.
Final note...
Below is the "custom template" path structure we have it setup as. Located in the 'enterprise' directory, so my custom files would be located:
/app/design/frontend/enterprise/custom_template/layout/catalogsearch.xml
/app/design/frontend/enterprise/custom_template/template/catalogsearch/form.mini.phtml
Hope this makes sense and helps.