Potresti usare un array di Boolean, della stessa dimensione del mazzo (cioè 112 elementi). Ogni volta che estrai un numero metti il valore True nel rispettivo elemento, in modo da escludere quella carta nell'estrazione seguente.

L'algoritmo da te proposto ad ogni estrazione di una carta diventa via via sempre più lento, in quanto sarà sempre più difficile estrarre carte "nuove".

Se io fossi in te opterei per un algoritmo un po' più "furbo": carico le carte in una collection (per esempio una List) e creo un'altra collection vuota, dove metterò le carte prese a caso dal primo mazzo. Con un ciclo for rimuovo un elemento a caso dalla prima collection e lo aggiungo alla seconda. Per capirci qualcosa tipo questo:
codice:
        Dim i, j As Integer
        Dim r As New Random

        'creo la collection iniziale
        Dim mazzo1 As New List(Of Integer)

        'popolo la collection
        For i = 1 To 112
            mazzo1.Add(i)
        Next

        'creo la collection di destinazione
        Dim mazzo2 As New List(Of Integer)

        For i = 1 To 112
            'indice casuale all'interno di mazzo1
            j = r.Next(0, mazzo1.Count)

            'sposto l'elemento
            mazzo2.Add(mazzo1(j))
            mazzo1.RemoveAt(j)
        Next