consulta con limit es muy lenta

[primary]

Me intento explicar, esta consulta es para un paginador entonces usando la consulta que tengo la que postee arriba la primera página seria con el limit 0,300.
La segunda página seria limit 200,200 así sucesivamente para cada página.
Pero que pasa con la consulta que me proponéis si quiero mostrar la primera página no pasa nada pero para la segunda si algún registro esta marcado como eliminado no me muestra los registros que pertenece es decir para la primera página no sería problema para la segunda seria así id>200 limit 200 pero que pasa si antes de los 200 registros tengo id como eliminados, si fuera así por ejemplo uno eliminado esta segunda página me mostraría un registro repetido con anterioridad en ja primera página, no se si se entiendo el problema.
En este caso tendría que crear una consulta antes para comprobar si ahí id eliminados en el ejemplo que puse para paginar la segunda página teniendo en cuenta que ahi un id eliminado la segunda consulta que seria el select seria así id>201 limit 200.
Entonces mi oregunta es, Es aconsejable crear dos consultas?