Alright, finally back to coding. Got it working with your help, though there is still a problem with the .Refresh() calls lagging the whole assembly. When I remove the whole refresh code, it becomes smooth and fast.

Main non-UI Thread:
Code:
    Private Sub task_MapoutDirectories()

        Dim var_newList As New List(Of String) : var_newList.AddRange(var_locList)
        Dim var_tempList As New List(Of String)
        Dim var_done As Boolean = False

        Do
            For Each var_location In var_newList
                Try 'Permision exceptions can pop up
                    var_tempList.AddRange(Directory.EnumerateDirectories(var_location, "*", SearchOption.TopDirectoryOnly).ToList)
                Catch ex As Exception
                End Try
            Next

            If var_tempList.Count = 0 Then
                var_done = True
            Else
                var_newList.Clear()
                var_newList.AddRange(var_tempList)
                var_dirList.AddRange(var_tempList)
                var_tempList.Clear()
            End If

            sub_refreshLabel(String.Concat("Directories found: ", var_dirList.Count), statusWindow.obj_C_label.Text, statusWindow.obj_D_label.Text, statusWindow.obj_statPBar.Value)
        Loop Until var_done

        'Directory search complete
        sub_editForms("Searching through directories", False, ProgressBarStyle.Continuous, 0, False)
        var_finishTime.Add(String.Concat("Directory mapping complete: ", CStr(DateTime.UtcNow)))

        'Start second task
        thread_fileSearch = New Threading.Thread(AddressOf task_findFiles)
        thread_fileSearch.Name = "fileSearch Thread"
        thread_fileSearch.IsBackground = True
        thread_fileSearch.Start()
    End Sub
Sub that refreshes the label and a progress bar is sub_refreshLabel (obviously):

Code:
    Private Sub sub_refreshLabel(ByVal var_B_text As String, ByVal var_C_text As String, ByVal var_D_text As String, var_pBarVal As Integer)

        If Me.InvokeRequired Then
            Me.BeginInvoke(Sub() sub_refreshLabel(var_B_text, var_C_text, var_D_text, var_pBarVal))
        Else
            statusWindow.obj_B_label.Text = var_B_text
            statusWindow.obj_C_label.Text = var_C_text
            statusWindow.obj_D_label.Text = var_D_text
            statusWindow.obj_statPBar.Value = var_pBarVal
            statusWindow.Refresh()
        End If
    End Sub
I'm going to work on it, but I'm open to any suggestions.