almost sounds like it may be doing a table scan every time it needs to get another page of rows

you could try to do analyze the queries to see whats actually going on