Aaron Erickson, a fellow Magenic consultant, has done a lot of research and work on how to index LINQ queries over objects. He just published an article on the topic: Indexed LINQ.

While indexing these queries has a cost, due to building the index, it can be very beneficial if you are doing a lot of queries over a large set of data.