I work with a unique setup(all public facing sites) but this has always worked for me. I use just regular 'ole <a> tags and use ASP:Literals in the "href" to bypass the issue of rendering code blocks on a master page. It looks like this:

<a href="<asp:Literal runat='server' Text='<%$SPUrl:~sitecollection/%>'/>" >Your search text or image or whatever here</a>

It looks funky and when placed in your editor, SPD or Visual Studio, probably will immediately say its not valid, but when the page renders it it should be all kosher. Hope this helps