Suponte que le envias una posicion menor que el tamaño de la estructura. ¿No estarias redimensionando luego una estructura de menor tamaño?
Creo (creo...) que deberias crear la variable j como global a ese procedimiento, para poder compararlo siempre con la posicion enviada.
Hecho esto, puedes crear un array "posiciones" de "j" campos, y con un bucle recorrerlos desde "i = 0" hasta "j". Yo cambiaria la estructura para que quedara de este modo:
Public Sub añadir(ByVal name As String, ByVal number As String, ByVal position As String)
Static j As Integer
j = CInt(position)
agenda(j).nombre = name
agenda(j).numero = number
agenda(j).posicion = position
agenda(j).booleano = true
ReDim Preserve agenda(j)
End Sub
Asi, al recorrer el array como te he dicho antes solo tienes que comprovar si el valor es true o false para saber si la posicion esta o no metida.
Espero haber sido de ayuda (y que te haya quedado claro xDD),