Hola:
No es un tema para descerebrarse... Un rollover no es otra cosa que cambiar una imagen, y lo respuesta que has encontrado es simplemente el primero de los párrafos de mi respuesta...
Con respecto al tag button, es igual a los botones creados con el tag input (type=button/reset/submit), pero en vez de un atributo value el contenido se pone antes del cierre como los tags normales (</button>)... con tu mismo ejemplo, hubiera bastado con cambiar el tag a y su atributo href, por el tag button del tipo submit...
Código:
<button class="enlace" type="submit" >
<img src="images/search.gif" onmouseover="this.src='images/search2.gif'" onmouseout="this.src='images/search.gif';" title="Make Search"/>
</button>
La definición de la clase enlace seguramente deba ser algo distinta de lo que tienes (cursor: pointer; border: 0; background-color: transparent... y tal vez margin:0; padding: 0;...)
Saludos
