I struggled with the same problem. When I set the AutoUpgradeEnabled to True, it started working better. But I added the below code and it seems to always works now.

Public Class frmSample

	Dim openFileDialog1 As New OpenFileDialog()

	Dim sTemp As String

    Private Sub btnOpen\_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)       Handles btnOpen.Click

    	openFileDialog1.AutoUpgradeEnabled = True

    	sTemp = "None"
    	sTemp = OpenDir()
    	Do Until sTemp <> "None"
        		'Nothing
    	Loop
	'The above loop is my solution.
	'It makes sure that the initial directory is known, before 
            'continuing to If OpenFileDialog1.ShowDialog

    	openFileDialog1.Filter = "txt files (\*.txt)|\*.txt|All files (\*.\*)|\*.\*"
    	openFileDialog1.FilterIndex = 0
    	openFileDialog1.RestoreDirectory = True

    	If openFileDialog1.ShowDialog() = System.Windows.Forms.DialogResult.OK Then

        		'Enter your code

    	End If

	End Sub

    Private Function OpenDir() As String

    	openFileDialog1.InitialDirectory = "C:\\Sample Initial Directory"
    	Return "OpenDir"

	End Function

End Class