You can create a small class to hold the key and value, and then store objects of that class in the collection.
Class KeyValue:
Public key As String
Public value As String
Public Sub Init(k As String, v As String)
key = k
value = v
End Sub
Then to use it:
Public Sub Test()
Dim col As Collection, kv As KeyValue
Set col = New Collection
Store col, "first key", "first string"
Store col, "second key", "second string"
Store col, "third key", "third string"
For Each kv In col
Debug.Print kv.key, kv.value
Next kv
End Sub
Private Sub Store(col As Collection, k As String, v As String)
If (Contains(col, k)) Then
Set kv = col(k)
kv.value = v
Else
Set kv = New KeyValue
kv.Init k, v
col.Add kv, k
End If
End Sub
Private Function Contains(col As Collection, key As String) As Boolean
On Error GoTo NotFound
Dim itm As Object
Set itm = col(key)
Contains = True
MyExit:
Exit Function
NotFound:
Contains = False
Resume MyExit
End Function
This is of course similar to the Dictionary suggestion, except without any external dependencies. The class can be made more complex as needed if you want to store more information.