While I'm pretty certain that the keys are unordered when returned from LINQ's ToLookup() method, is the order of values preserved? I can't find any documentation that says one way or the other.
The current implementation of ToLookup() does indeed preserve the order of the values (check the implementation of Lookup<TKey,TElement>.Grouping<TKey,TElement>.Add()), but I do not believe it is guaranteed to stay that way. To guarantee ordering, your best bet is probably to include the element's original index, perhaps using Select's with-index overload, and then sort again.