Well, I haven't tried it, but what I would look at in head.tpl is around line 17
Code:
<TD class="HeadLine" height="22">
{if $usertype eq "C"}
{ include file="customer/search.tpl" }
{/if}
</TD>
I am assuming you are using this search.tpl for your search layout. If so, just make a new table (1R, 2C) inside the TD and then put the search call inside one set of TDs and then call in the minicart.tpl in the other.
*should* work.
How are you calling minicart into the head now?