Search a big (13 GB) Outlook PST file
I would assume that this
For Each d As KeyValuePair(Of String, String) In dict
    Using outputFile As New StreamWriter(&quot;E:\&quot; &amp; Convert.ToString(&quot;file.txt&quot;), True)
        outputFile.WriteLine(d.Key &amp; &quot;,&quot; &amp; d.Value)
    End Using
Next  

is the bottleneck of your code. You are opening, writing to and closeing the file for each KeyValuePair of the dictionary.
Change it like
Using outputFile As New StreamWriter(&quot;E:\&quot; &amp; Convert.ToString(&quot;file.txt&quot;), True)
    For Each d As KeyValuePair(Of String, String) In dict
            outputFile.WriteLine(d.Key &amp; &quot;,&quot; &amp; d.Value)
    Next
End Using  

and it should be running much faster.
Btw, why do you use Convert.ToString(&quot;file.txt&quot;) ?

InitIndexing()
by changing the condition of the f.Folders.Count to check if Count = 0 you could return early from the Sub and therefor save one level of indentation like so
If f.Folders.Count = 0 Then Exit Sub

For c = 1 To f.Folders.Count
    Dim Folder As Outlook.Folder = f.Folders.Item(c)
    Dim r As String = Folder.FolderPath
    For Each ml In Folder.Items
        oPA = ml.PropertyAccessor
        skey = oPA.BinaryToString(oPA.GetProperty(PropName))
        If Not dict.ContainsKey(skey) Then
            dict.Add(skey, r)
        End If
    Next
    Call InitIndexing(Folder)
Next  

but you have bigger problems here: Naming ! You shouldn't use abbreviations to name things. If you come back to this code in 3 months you won't know the meaning of oPA, r or objName. You should always use meaningful names to name things.