Yeah, you already pretty much know the answer to your own question. It has a lot to do with trade-offs, whether or not you decide to preload everything depends on how much "everything" really is. If it takes less than a second, generally preloading is a wonderful improvement. Now, assume the impossibility that Google preloaded every possible search result. That's obviously not going to work, so (like you said), loading the first 10 results (or the first few pages each with 10 results) will be a great improvement over trying to preload billions of results.
Basically, the best you can do is test and use good judgement. Which is faster? Is it ever unbearably slow? Use timers and iteration tests where you see fit to see where the load-time is being consumed.
I probably didn't help much, you already knew all this- I can tell when u asked if you should show the first 10 or what.. I mean, there's no -right- answer. It's just give/take ajax vs preload until you like the result. One thing I never like is the traditional site where you have to click a link and reload the whole entire page when all that changed was a little thing.. I use ajax in all my sites now rather than the traditional methods. AJAX isn't the matter though- We always need AJAX eventually. The real question is, should we preload 'x' data up-front or wait until it's requested?