View page source on the rendered page.
I'm almost positive thats where your perf issues are coming from. The ViewState works by serializing/encoding its contents and sticking them on a hidden field. Both Partial and Full page postbacks will push the viewstate over the wire in both directions.
There are a bunch of places you can store stuff in asp, each has its pro's and con's. First thing though is are you using the automagical (like editing) stuff in your grid, or is it display only? If it is display only, stick EnableViewState="False" in it, that will make a big difference.
As for the search results, If it is something that will be the same for everyone (not based on dynamic criteria), I would stick it in the cache object. If it is the results of a search screen, I would probably use the session, not the view state. Filling up the session is still not that great, as it is in-proc memory for each active user, but in this case it is probably a better then serializing to the page. General rule of thumb is ViewState for smaller things, Session for bigger things (not quite that simple, but it is better then just viewstate for everything)