How to Generate Many Random Various Numbers?

Assuming the range of numbers is small, and all of them are required in the result (those are the assumptions implied by your code), and with a small change in the API definition, a much more compact and faster implementation would be this:

public IList<int> randomPermutation(int min, int max) {
    Random r=new Random();
    SortedList<int, int> perm=new SortedList<int, int>();
    for (int i=min; i<=max; i++) perm.Add(r.Next(), i);
    return perm.Values;
}

BTW: If the size of the number set were to increase above 100, I would consider switching to a Dictionary<int,int> and sorting it at the end (the code shown spends cycles keeping the SortedList<int,int> sorted while it is being populated).

:)