手前味噌ですが、実装例がこのあたりにあります。
http://rucio.cloudapp.net/ThreadDetail.aspx?ThreadId=9982

とはいえ古いコードですので、折角なので現行バージョンっぽい書き方にしてみました。
VB2012 以降が必要です。

Imports System.IO
Module Module1
    Public Sub Main()
        'これだと、権限エラー(UnauthorizedAccessException)等で止まってしまうことが… 
        ' 
        'For Each s In Directory.EnumerateDirectories("D:\", "*", SearchOption.AllDirectories) 
        '    Console.WriteLine(s) 
        'Next 

        'こちらなら、アクセス権の無いディレクトリを読み飛ばして列挙しつづけます 
        ' 
        For Each s In SafeEnumerateDirectories("D:\", "*")
            Console.WriteLine(s)
        Next
    End Sub


    Public Iterator Function SafeEnumerateDirectories(ByVal parentDir As String, Optional ByVal seachPattern As String = "*") As IEnumerable(Of String)
        Dim directories As IEnumerable(Of String) = Nothing
        Try
            directories = Directory.EnumerateDirectories(parentDir, seachPattern, SearchOption.TopDirectoryOnly)
        Catch
            'Debug.WriteLine(parentDir) 
        End Try
        If directories Is Nothing Then
            Return
        Else
            For Each subDir In directories
                Yield subDir
                For Each recursive In SafeEnumerateDirectories(subDir, seachPattern)
                    Yield recursive
                Next
            Next
        End If
    End Function
End Module



元のコードは List(Of ) なため、列挙までに時間がかかりましたが、
今回は Iterator にしていますので、見つかった物から即時返却されはじめます。


なお、シンボリックリンクの中も探索する仕様なので、
親子が繋がった無限階層なパスの中も、延々と探し続けますのでご注意を。
（といっても、無限階層であれば、パス長エラーで打ち切られるはずですが）