Loading all the data at once is not necessarily all-bad in the sense that it has a lot of performance advantages. However, I would only use this method if:
- I was 100% certain that this list would not grow to large amounts
Most often than not, I can't guarantee that the list would not grow, so I usually have to stick with the second solution you mentioned. Load by page on demand. This also means you cannot search using the items you have available unless searching for items on the current page only is acceptable. Searching must perform its own query on the database separate from the cache you have.
I would not bother to cache pages you've already loaded, since how often do you return to previous pages after you've seen them? It is not worth the loss of memory in my humble opinion. Rather, I would advise you to load several pages at once rather than just one at a time. When the user clicks next and nothing is loaded, you fetch the next 4 pages. This way, nothing must be fetched for the following 3. This is already a solution that would meet most of your requirements and still be 4 times as efficient than fetching one page at a time.
If you want to get even more sophisticated, you would use AJAX to load the next page once the user has loaded the current page. You only have to perform a check that the next page has already been loaded before showing the next page, which hopefully enough time will elapse that it will have already been loaded. And in the case in which it has not yet been loaded, you can show some sort of load animation to provide feedback to the user that you're currently working on it. This has the best performance of all solutions, however it is also the most difficult to implement.
Hope that helps!