The nature of "Random numbers" is that they do not in any way guarantee uniqueness in a small set like yours: in fact they can never guarantee uniqueness regardless of the sample size - the next number has no relation to the previous ones except statistically.
And creating your random generator instance inside the loop doesn't help, because it is preset from the system clock, so it's very likely that multiple instances will start with the same value (given that Random is not truly random, it's pseudo random like all software based random number generators).
If you want to draw from a pool of unique numbers only, then set up an new List<int> and fill it with the range of values. Then use that to provide your unique string:
private Random randomGenerator = new Random();
public List<string> GetRandomRecords(List<string> records, int requiredRecords)
{
int numberOfRecords = records.Count;
List<string> randomRecords = new List<string>();
List<int> indexes = Enumerable.Range(0, requiredRecords).ToList();
for (int i = 0; i < requiredRecords; i++)
{
int randomIndex = randomGenerator.Next(0, indexes.Count);
int index = indexes[randomIndex];
indexes.RemoveAt(randomIndex);
string record = records[index];
randomRecords.Add(record);
}
return randomRecords;
}
}