Assuming you can have one or more space afer <a, and zero or more space around the = signs, the following should work:
$ cat in.txt
<a href="http://www.wowhead.com/?search=Superior Mana Oil">
<a href="http://www.wowhead.com/?search=Tabard of Brute Force">
<a href="http://www.wowhead.com/?search=Tabard of the Wyrmrest Accord">
<a href="http://www.wowhead.com/?search=Tattered Hexcloth Sack">
#
# The command to do the substitution
#
$ sed -e 's#<a[ \t][ \t]*href[ \t]*=[ \t]*".*search[ \t]*=[ \t]*\([^"]*\)">#&\1</a>#' in.txt
<a href="http://www.wowhead.com/?search=Superior Mana Oil">Superior Mana Oil</a>
<a href="http://www.wowhead.com/?search=Tabard of Brute Force">Tabard of Brute Force</a>
<a href="http://www.wowhead.com/?search=Tabard of the Wyrmrest Accord">Tabard of the Wyrmrest Accord</a>
<a href="http://www.wowhead.com/?search=Tattered Hexcloth Sack">Tattered Hexcloth Sack</a>
If you're sure you don't have the extra spaces, the pattern simplifies to:
s#<a href=".*search=\([^"]*\)">#&\1</a>#
In sed, s followed by any character (# in this case) starts substitution. The pattern to be substituted is until the second appearance of the same character. So, in our second example, the pattern to be substituted is: <a href=".*search=\([^"]*\)">. I used \([^"]*\) to mean, any sequence of non-" characters, and saved it in backreference \1 (the \(\) pair denotes a backreference). Finally, the next token delimited by # is the replacement. & in sed stands for "whatever matched", which in this case is the whole line, and \1 just matches the link text.
Here's the pattern again:
's#<a[ \t][ \t]*href[ \t]*=[ \t]*".*search[ \t]*=[ \t]*\([^"]*\)">#&\1</a>#'
and its explanation:
' quote so as to avoid shell interpreting the characters
s substitute
# delimiter
<a[ \t][ \t]* <a followed by one or more whitespace
href[ \t][ \t]*=[ \t]* href followed by optional space, = followed by optional space
".*search[ \t]*=[ \t]* " followed by as many characters as needed, followed by
search, optional space, =, followed by optional space
\([^"]*\) a sequence of non-" characters, saved in \1
"> followed by ">
# delimiter, replacement pattern starts
&\1 the matched pattern, followed by backreference \1.
</a> end the </a> tag
# end delimiter
' end quote
If you're really sure that there will always be search= followed by the text you want, you can do:
$ sed -e 's#.*search=\(.*\)">#&\1</a>#'
Hope that helps.