Solo tienes que pasar en los links de las páginas, la variable de búsqueda.
Ej. para la "página siguiente":
[<A HREF="usuariosencontrados.asp?pagina=<%=pagina_act ual+1%>&letradelnombre=<%=request.querystring("let ra")%>" onMouseOver="window.status='Página siguiente';return true;" onMouseOut="window.status='';return;"><< Anterior</A>]