Puoi fare benissimo un ArrayList di strutture, ma ti consiglio una lista fortemente tipizzata.

codice:
Structure Contatto
    Dim Nome As String
    Dim Cognome As String
End Structure

Dim Contatti As New List (Of Contatto)

Public Sub Aggiungi(ByVal Nome As String, ByVal Cognome As String)
    Dim buff As Contatto
    buff.Nome = Nome
    buff.Cognome = Cognome
    Contatti.Add(buff)
End Sub
Per tuttel e funzioni della List MSDN è tuo amico