A minha sugestão é que você pegar o dia e o mês como vectores numéricos. Você armazena o número de cada parte gerada em vectores e percorrer os vectores para evitar repetição dos numeros gerados.
O seguinte código de VBA gera um número e guarde em um vector numérico. Você pode obter idéias a partir daí.
Public Function NumeroAleatorio(Superior As Integer, _
Optional Baixa As Integer = 1, _
Optional Quantas As Integer = 1, _
Optional Unico As Boolean = True) As Variant
'*******************************************************
'Esta função gera um vector aleatória de
'Números entre Baixa e Alta
'Além parâmetros podem incluir se quer
'Valores Unicos
'Observe o resultado é, inclusive, dos extremos
'Exemplo de Debug :
'x = NumeroAleatorio(49, 1, 7)
'For n = LBound(x) To UBound(x): Debug.Print x(n);: Next n
'ADVERTÊNCIA Quantas deve ser maior que (Superior - Baixa)
'******************************************************
On Error GoTo LocalError
If Quantas > ((Superior + 1) - (Baixa - 1)) Then Exit Function
Dim x As Integer
Dim n As Integer
Dim vecNums() As Variant
Dim colNumeros As New Collection
ReDim vecNums(Quantas - 1)
With colNumeros
'Em primeiro lugar preencher a coleção
For x = Baixa To Superior
.Add x
Next x
For x = 0 To Quantas - 1
n = NumeroAleatorio(0, colNumeros.Count + 1)
vecNums(x) = colNumeros(n)
If Unico Then
colNumeros .Remove n
End If
Next x
End With
Set colNumeros = Nothing
NumeroAleatorio = vecNums
Exit Function
LocalError:
'(Por Caso de erro)
NumeroAleatorio = ""
End Function
Public Function NumeroAleatorio(Superior As Integer, _
Baixa As Integer) As Integer
'Gera a numeros aleatorios entre valores Baixa and Superior
Randomize
NumeroAleatorio = Int((Superior - Baixa + 1) * Rnd + Baixa )
End Function