En realidad, lo peor no es que no se borren los datos de los textbox (que no solo no importa si no que interesa conservarlo temporalmente)... lo peor es que no se borran de tu array.

Hay una variedad de indicaciones que dar y corregir... pero no quiero extenderme en explicaciones... porque son elementales y uno debiera ceñirse a ellos.

Te pòngo un código que puedes remplazar por todo lo que tienes. nota que he renombrado los textbox y los botones a un valor más acorde y el boton 'nuevo', en realidad sobra, aún así su código todavía es válido.

Nota también, que si no tienes más módulos de código donde uses esos registros de la agenda, el código en el módulo puede ser pasado al formulario (pero con alcance privado).

 
Private Type Registro
    Nombre                  As String * 15
    Apellidos               As String * 25
    Telefono                As String * 15
    Edad                    As String * 3
End Type
 
Private Agenda(0 To 49)     As Registro
Private totalregistros      As Integer
Private NoUpdateTxts        As Boolean
 
 
Private Sub BtnAñadir_Click()
    If (totalregistros = 50) Then
        MsgBox "lista completa", 16, "error"
    Else
        If (Esregistrable = True) Then
            With Agenda(totalregistros)
                .Nombre = TxtNombre.Text
                .Apellidos = TxtApellidos.Text
                .Telefono = TxtTelefono.Text
                .Edad = Val(TxtEdad.Text)
            End With
 
            Combo2.AddItem TxtNombre.Text
            totalregistros = (totalregistros + 1)
 
            Call BtnNuevo_Click
        Else
            MsgBox "El registor está incompleto, no puede añadirse hasta que esté completo."
        End If
    End If
End Sub
 
Private Sub BtnEliminar_Click()
    Dim b As VbMsgBoxResult
    Dim index As Integer, k As Integer, j As Integer
 
    j = (Combo2.ListCount - 1)
    index = Combo2.ListIndex
    If (index = -1) Then  ' exit sub
        Combo2.ListIndex = j  ' si no hay ninguno seleccionado se supone el último.
        index = j
    End If
 
    b = MsgBox("Eliminar Registro: " + TxtNombre.Text, 3 + 32, "Eliminar")
    If (b = vbYes) Then
        ' Los datos a eliminar, se pasan a los textbox, por si se quiere volver a añadir o editar antes de añadir.
        Call Combo2_Click
        ' opcionalmente se puede simplemente borrar...
        'Call BtnNuevo_Click
 
        ' Eliminar el item del combo.
        Combo2.RemoveItem (index)
 
        ' Bajar todos los items en el array por encima del item eliminado una posición.
        For k = index To j - 1
            Agenda(k) = Agenda(k + 1)
        Next
 
        ' ahora el último ítem queda libre, se puede vaciar o dejarlo...
        With Agenda(k)
            .Nombre = ""
            .Apellidos = ""
            .Telefono = ""
            .Edad = ""
        End With
 
        ' queremos que en el combo siempre se vea un item.
        NoUpdateTxts = True
        If (j > 0) Then
            If (index < j) Then
                Combo2.ListIndex = index
            Else
                Combo2.ListIndex = (j - 1)
            End If
        End If
        NoUpdateTxts = False
 
        totalregistros = j ' descontar 1.
 
        ' Desactivar el botón eliminar si no quedan registros.
        BtnEliminar.Enabled = (totalregistros > 0)
    End If
End Sub
 
Private Sub BtnTerminar_Click()
    End
End Sub
 
Private Sub BtnNuevo_Click()
    TxtNombre.Text = ""
    TxtApellidos.Text = ""
    TxtTelefono.Text = ""
    TxtEdad.Text = ""
    TxtNombre.SetFocus
End Sub
 
Private Sub Combo2_Click()
    If (NoUpdateTxts = False) Then
        With Agenda(Combo2.ListIndex)
            TxtNombre.Text = .Nombre
            TxtApellidos.Text = .Apellidos
            TxtTelefono.Text = .Telefono
            TxtEdad.Text = Val(.Edad)
        End With
    End If
End Sub
 
Private Sub TxtEdad_GotFocus()
    Call SelOnGotFocus(TxtEdad)
End Sub
 
Private Sub TxtApellidos_GotFocus()
    Call SelOnGotFocus(TxtApellidos)
End Sub
 
Private Sub TxtNombre_GotFocus()
    Call SelOnGotFocus(TxtNombre)
End Sub
 
Private Sub TxtTelefono_GotFocus()
    Call SelOnGotFocus(TxtTelefono)
End Sub
 
Private Sub SelOnGotFocus(ByRef Txt As TextBox)
    Txt.SelStart = 0
    Txt.SelLength = Len(Txt.Text)
End Sub
 
' Verifica que los campos dle registor no quedan vacíos (sdon obligatorios)
'  Si un campo no es obligatorio, debe retirarse de aquí.
Private Function Esregistrable() As Boolean
    If (Len(Me.TxtNombre.Text) > 0) Then
        If (Len(Me.TxtApellidos.Text) > 0) Then
            If (Len(Me.TxtTelefono.Text) > 0) Then
                Esregistrable = IsNumeric(Me.TxtEdad.Text)
            End If
        End If
    End If
End Function
 
'Private Sub Form_Load()
'    totalregistros = 0
'End Sub
 

Ejecuta el código paso a paso al menos el del botón eliminar, para ver qué va sucediendo a cada instante... (arranca la aplicación con la tecla F8, o bien pon un punto de interrupción (tecla F9) en la línea del boton eliminar y cuando llegue allí se parará y entonces ejecuta paso a paso con la tecla F8).


Por favor, como ya llevas tiempo en el foro, acostumbra a colocar tu código entre etiquetas GESHI (elige VB), que aparecen en el editor cuando redactas tu mensaje...