Deserialize an email header into key-value pairs
There are a couple of things that I find odd about this code. This is the first thing that jumps out at me. 


Dim startIndex As Integer = Nothing
Dim item As Match = Nothing
Dim key As String = Nothing



I see no purpose in initializing variable to Nothing. Simply declaring them would be cleaner in my opinion. 

Dim startIndex As Integer
Dim item as Match
Dim key As String




I also find your For loop a bit strange. Is there a reason you're stepping backwards? If there is, I don't see it and you should comment on why in the code. 


For index As Integer = (matches.Count - 1) To 0 Step -1



Personally, I would rewrite this to loop forward like this. 

For index As Integer = 0 To matches.Count - 1
    '...
Next index




You could also use a comment here. 


Const pattern As String = "(\n|^)[a-z|A-Z|-]*:\s"



Regular Expression patterns are rarely obvious. Tell Mr. Maintainer in English what you're matching on.