Optimizing List<string> performance

I have a List being stored in my cache with about 600K members. I want this to act as the backend for an Ajax autocomplete box. It's accessible through my model:

public static List GetProducts()
{            
    var cached = HttpContext.Current.Cache["MyApp-Products"];
    if (cached == null)
    {
        UpdateCache();
        return GetProducts();
    }
    return ((List)cached);
}

My ajax call uses this method to get it's data:

[HttpPost]
public JsonResult ProductSearch(string term)
{
    return Json(MyModel.GetProducts()
        .Where(s => s.ToUpper().StartsWith(term.ToUpper()))
        .OrderBy(s => s)
        .Take(5)
        .ToList()
    );
}

The problem is, this Ajax call to ProductSearch() is waiting 2.09 seconds for a response. I'm doing the same with other objects in my model that have smaller list sizes and they respond in 35-125ms (which is acceptable).

So, I believe my performance issue is somewhere in accessing the list. Is there a faster way to access this list besides the Linq code that I'm using, or just a better way to use Linq?

A starts-with should be easy enough to store in a pre-sorted list, ideally using a case-insensitive sort comparer rather than applying conversions each sort. Then: use binary search to find the first match, and keep moving forwards until it no longer matches. Should be pretty efficient.

If this needs to be edited in a shared multi-threaded context, be sure to use appropriate synchronization - presumably readers will be more common than writers, so a ReaderWriterLockSlim may be the best option.

StackExchange Code Review Q#9773, answer score: 17