How to generate a sequence of numbers while respecting some constraints?

[I've overwritten an earlier, wrong solution based on a misunderstanding of the problem].

---

We start by making a helper method that produces a shuffled range based on a given seed:

static IEnumerable<int> ShuffledRange(int size, int seed)
{
  var rnd = new Random(seed);
  return Enumerable.Range(0, size).OrderBy(p => rnd.Next());
}

The next thing we're going to do is to randomize all the suffixes and get all of them into a sequence. Note that we use a different seed for each shuffle, but the value of the seed is predictable.

static IEnumerable<string> ShuffledIds(int seed)
{
  const int s = 10000;
  const int p = 100;
  var suffixes = Enumerable.Range(0, p)
    .Select(seedOffset => ShuffledRange(s, seed + seedOffset)
    .SelectMany(x => x);

We've met the constraint that each chunk of 10000 has all 10000 suffixes, in random order. Now we have to distribute 10000 of each prefix. Let's make a sequence of prefixes for each possible suffix. (Again, we use a not-yet-used seed for each shuffle.)

  var dict = new Dictionary<int, IEnumerator<int>>();
  for (int suffix = 0; suffix < s; suffix += 1)
    dict[suffix] = ShuffledRange(p, seed + p + suffix).GetEnumerator();

And now we can distribute them

  foreach(int suffix in suffixes)
  {
    dict[suffix].MoveNext();
    yield return dict[suffix].Current.ToString("d2") +
     suffix.ToString("d4");
  }
}

And that should do it.

Notice that this also has the nice property that the shuffling algorithm is no longer the concern of the code which needs shuffles. Try to encapsulate details like that in helper functions.

Using the idea posted by ckuri and including the imporvements suggested by Eric Lippert, you can group the list of numbers by suffix:

var prefixLength = 100;
var suffixLength = 10000;

 Enumerable
  .Range(0, prefixLength * suffixLength)
  .OrderBy(number => rnd.Next())
  .GroupBy(number => number % suffixLength)

Then, you can flatten the list:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)

Until here, you will have a list of numbers, where, in each 100 lines (prefixLength), the prefixes will be the same. So, you can select them, getting the index of each line:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)
 .Select((g, index) => new { Index = index, Number = g })

Using the index information, you can group the lines applying the mod function, using the prefixLength as a factor:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)
 .Select((g, index) => new { Index = index, Number = g })
 .GroupBy(g => g.Index % prefixLength, g => g.Number)

Finally, you can flatten the list again, and convert the values to string, in order to get the final result:

Enumerable
 .Range(0, prefixLength * suffixLength)
 .OrderBy(number => rnd.Next())
 .GroupBy(number => number % suffixLength)
 .SelectMany(g => g)
 .Select((g, index) => new { Index = index, Number = g })
 .GroupBy(g => g.Index % prefixLength, g => g.Number)
 .SelectMany(g => g)
 .Select(number => $"{number/suffixLength:d2}{number%suffixLength:d4}")