Можно ли в качестве keySelector при вызове IEnumerable.OrderBy использовать недетерминированную функцию, т.е. такую, которая не обязательно вернет один и тот же ключ, будучи вызвана дважды для одного элемента?

С одной стороны, то, что OrderBy вычисляет и кеширует ключи элементов перед сортировкой — это вроде деталь реализации, но с другой — в документации к OrderBy на keySelector не налагается никаких требований, кроме того чтобы для возвращаемых значений ключа существовал Comparer<TKey>.Default.