Great point. You could could progressively backfill the search to protect the initial load and user experience. You could cut down on overall bandwidth by only backfilling search data if the user has shown a preference for using search. The first search experience is a little slower, but overall system work and client side implementation using the posted method could provide a good balance.

One example I can think of is searching for matching documents with some other method (on the server side), and then searching inside each document with this method.

but what if you had an infinite scroll ala twitter feed? then you can do client side search on that list without going back to the server.