unpredictable behavior with pagination of search results with duplicates

When searching for contacts in multiple groups (that have overlap) and result in more than 500 results, when I hit page 10 I get returned to the advanced search screen with the message that no records could be found.

It seems that when we hit 500, the prev_next cache is populated incorrectly. I think it is supposed to take the next 500 records, but instead it takes the next 1000. In addition (and I think this is the source of the problem) it adds duplicate records to the prev next cache.