What are best practices for caching paginated results whose ordering/properties can change?

It seems what you need is a wrapper for all the parameters that define a page (say, pageNumber, pageSize, sortType, totalCount, etc.) and use this DataRequest object as the key for your caching mechanism. From this point you have a number of options to handle the cache invalidation:

• Implement some sort of timeout mechanism (TTL) to refresh the cache (based on how often the data changes).
• Have a listener that checks database changes and updates the cache based the above parameters (data refresh by server intent).
• If the changes are done by the same process, you can always mark the cache as outdated with every change and check this flag when a page is requested (data refresh by client intent).

The first two might involve a scheduler mechanism to trigger on some interval or based on an event. The last one might be the simpler if you have a single data access point. Lastly, it can quickly become an overly complicated algorithm that outweighs the benefits, so be sure the gain in performance justify the complexity of the algorithm.