Старый пост наверняка, но я просто использую GUID.
Items = Items.OrderBy(o => Guid.NewGuid().ToString()).ToList();
GUID всегда уникален, и поскольку он регенерируется каждый раз, когда результат изменяется каждый раз.