I fixed it in the end by copying the getPagination, getTotal, getItems etc. from the library's (list.php) and into my model (to override them). Then in each method, I made sure the results where returned instead of sending them to the cache.
The getTotal function seems to count the number of rows instead of doing a seperate count(*). That's ok with a few thousand records but over 1/2 million is asking for trouble!