Using the ASP.NET cache is fine. Session is faster serializing and deserializing the data though.
I think using the cache with a 2-3 minute sliding expiration, is probably the best option off the top of my head. This would make sure that you are not leaving lots of data in memory for extended periods of time while still addressing your needs for postbacks sorting data etc...
Even at 4000+ records for larger reports, with 5-10 users you still won't come close having issues with memory. I'd double check my queries and make 100% sure you need each and every column though.