Puedes utilizar esto:
Sub CODIGOOS()
vuelta:
Dim VVV As String
Dim vd As String
Dim vg As String
For B = 1 To 4
VVV = Int((90 - 65 + 1) * Rnd + 65)
vs = Chr(VVV)
vd = vs & vd
Next
VVV = Int((99 - 11 + 1) * Rnd + 11)
codigo = vd & VVV
For B = 1 To 65000
vg = Worksheets("Hoja2").Range("A" & B).Value
If IsNull(vg) Or vg = "" Then
Worksheets("Hoja2").Range("A" & B).Value = codigo
MsgBox codigo
GoTo endd
End If
If codigo = vg Then
GoTo vuelta
End If
Next
endd:
End Sub
Lo que hago es generar el código con el formato de 4 letras y dos números y luego recorre desde A1 hasta A65000 de la hoja "Hoja2". Si encuentra el valor que acaba de generar vuelve al principio, si encuentra un espacio en blanco escribe el código que ha generado y lo muestra en pantalla.