I agree that an array of UDTs is probably not going to
give you any speed increase, because then you would
need to use some sort of ArrayDelete function which
would also slow things down.

One alternative to use Olaf Schmidt's Sorted Dictionary
object which keeps its collection sorted as items are
added, which allows a binary search.

http://www.thecommon.net/9.html

Code:
Option Explicit
Private Col As Collection
Private SD As dhSortedDictionary.cSortedDictionary
Private Declare Function GetTickCount Lib "kernel32" () As Long

Private Sub Form_Load()
 Dim i As Long, t As Long
 Dim Count As Long
 Set Col = New Collection
 Set SD = New cSortedDictionary
 Count = 100000
 For i = 1 To Count
  Col.Add "Item " & i, "k" & i
  SD.Add i, "Item " & i
 Next
 
 t = GetTickCount
 For i = Count \ 2 To Count
  Col.Remove "k" & i
 Next
 Debug.Print GetTickCount - t
 
 t = GetTickCount
 For i = Count \ 2 To Count
  SD.Remove i
 Next
 Debug.Print GetTickCount - t
 
End Sub
In my tests, the sorted dictionary code was more than twice as fast.