Both Firefox and IE have a mini search plugin in the top right corner of the window, for things like Google and such.
Armory already has come out with their own search plugin where you just type the name in and then it goes straight to the list of characters with that name.
I don't think it would be too hard to create a plugin for wow-heroes.
I believe that it is to be encoded in XML format.
And to correct for the realm problem, just have an options menu to re select and save the realm you would like to search by.