Yo lo que suelo hacer en estos casos, salvo que la lista de numeros sea muy grande es crear una lista con todos los numeros, ordenarla aleatoriamente y luego ir dropeando numeros desde el final de la lista.
No se como hacerlo en C# pero no tiene que ser muy complicado aplicar el concepto.

En python 2.6 seria algo asi:

import random
mylist = range(100)
random.shuffle(mylist)

#Y luego para ir sacando numeros con
aleatorio = mylist.pop()