C# LINQ executing the same work over and over

is it that LINQ is repeating the same work everytime studentsToRemoveRecords is iterated over, even though the resulting input values are identical each time?

Yes, that's the nature of LINQ. Some Visual Studio Extensions, like ReSharper, give you warnings when you create code that might lead to multiple iterations of a LINQ Query.

If you want to avoid it, do this:

var students = studentsToRemoveRecords.Select(x => x.CourseId)
                .Distinct()
                .SelectMany(c => studentRepository.GetStudentsOnCourse(c.Value))
                .ToList();

With ToList() the Query is executed immediately and the resulting entities are stored in a List<T>. Now you can iterate several times over students without having performance issues.

Edit to include comments:

Here is a link to some good documentation about it (thank you Sergio): LINQ Documentation

And some thoughts about your question how to handle this in a large code base: Well, there are reasons for both scenarios - direct execution and storing the result into a new list, and deferred execution. If you are familiar with SQL databases, you can think of a LINQ Query like a View or a Stored Procedure. You define what filtering/altering you want to execute on a base table to get the resulting entities. And each time you query that View/execute that Stored Procedure, it runs based on the current data in the base table.

Same for LINQ. Your Query (without ToList()) was just like the definition of the View. And each time you iterate over it, that definition gets executed based on the current Entities in studentsToRemoveRecords at that moment. And maybe that's your intetion. Maybe you know that this base list is altering and you want to execute your query several times, expecting different results. Then do it without ToList().

But when you want to execute your query only once and then expect an immutable result list over which you can iterate multiple times, do it with ToList().

So both Scenarios are valid. And when you iterate only once, both scenarios are equal (disclaimer: when you iterate directly after defining the query). Maybe that's why you saw it so many times like this. It depends what you want.

Unclear exactly how your classes are done, BUT:

public class Student
{
    public int Id { get; set; }
}

public class StudentCourse
{
    public int StudentId { get; set; }
    public int? CourseId { get; set; }
}

public class StudentRepository
{
    public StudentCourse[] StudentCourses = new[] 
    {
        new StudentCourse { CourseId = 1, StudentId = 100 },
        new StudentCourse { CourseId = 2, StudentId = 200 },
        new StudentCourse { CourseId = 3, StudentId = 300 },
        new StudentCourse { CourseId = 4, StudentId = 400 },
    };

    public Student[] GetStudentsOnCourse(int courseId)
    {
        Console.WriteLine($"{nameof(GetStudentsOnCourse)}({courseId})");
        return StudentCourses.Where(x => x.CourseId == courseId).Select(x => new Student { Id = x.StudentId }).ToArray();
    }
}

and then

static void Main(string[] args)
{
    var studentRepository = new StudentRepository();
    var studentsToRemoveRecords = studentRepository.StudentCourses.ToArray();

    var students = studentsToRemoveRecords.Select(x => x.CourseId)
                        .Distinct()
                        .SelectMany(c => studentRepository.GetStudentsOnCourse(c.Value));
                        //.ToArray();

    var studentsToRemove = new List<Student>();

    foreach (var record in studentsToRemoveRecords)
    {
        studentsToRemove.Add(
            students.Single(s => s.Id == record.StudentId));
    }
}

the method is called 16 times, with .ToArray() it is called 4 times. Note that .Single() will parse the full students collection to check that there is a single student with the "right" Id. Compare it with First() that will break after finding one record with the right Id (10 total calls of the method). As I've said in my comment, the method is called studentsToRemoveRecords.Count() * studentsToRemoveRecords.Distinct().Count(), so something like x ^ 2. Doing a .ToArray() "memoizes" the result of the GetStudentsOnCourse.

Just out of curiosity, you can add this class to your code:

public static class Tools
{
    public static IEnumerable<T> DebugEnumeration<T>(this IEnumerable<T> enu)
    {
        Console.WriteLine("Begin Enumeration");

        foreach (var res in enu)
        {
            yield return res;
        }
    }
}

and then do:

.SelectMany(c => studentRepository.GetStudentsOnCourse(c.Value))
.DebugEnumeration();

This will show you when the SelectMany is enumerated.