se me ocurre lo siguiente... al realizar la búsqueda:
Código:
conn.Execute("DELETE FROM tablaBusquedas WHERE id in(SELECT MIN(id) FROM tablaBusquedas)")
conn.Execute("INSERT INTO tablaBusquedas (campo) VALUES ('"& Request.Form("criterio_de_busqueda") &"') ")
el campo id sería un autonumérico, claro.