Pagination is ON for all our lists.
However, no value was specified for number of entries per page (effectively unlimited) and this seems to be the cause of the problem. I tested the list with various levels of "Number of entries per page" and the list worked fine up to 625. Thereafter, the error occurred.
It was never to be intended to be a list with an unlimited page length, having been originally set to 50 entries, but it seems to have been changed somewhere along the way.
I have reset all our lists to have "Number of entries per page" set to 50, the problem has gone away and can be considered resolved
Perhaps the 100-per-page recommended limit could be added to the help information for this field, and maybe you could use 0 for unlimited rather than blank, preset the default (30) and make the field mandatory?
For the benefit of others, I think the 'limit' of 625 probably only applies to our particular list which has 4 columns and five fields. Those users with more fields and/or fewer columns would probably find their 'limit' to have a different value.
Many thanks for your help.