Your method above only searches the current page of the GridView, if paging is enabled. To search the entire GridView, you need to look into its DataSource and use that to get the appropriate values.
In my case, I needed to give users a quick way to search for a specific client, so I added an AJAX enabled Combo Box, and OnSelectedIndexChanged, I used this to locate the appropriate GridView row and select it:
Dim i As Integer, DataSetIndex As Integer
Dim SelectedRowIndex As Integer
Dim dv As DataView = ObjectDataSourceClients.Select
Dim dt As DataTable = dv.ToTable
For i = 0 To dt.Rows.Count - 1
If dt.Rows(i)("Client_ID") = ComboBoxClientSearch.SelectedValue Then
DataSetIndex = i
Exit For
End If
Next
GridViewAllClients.PageIndex = DataSetIndex \ GridViewAllClients.PageSize
SelectedRowIndex = DataSetIndex - (GridViewAllClients.PageSize * GridViewAllClients.PageIndex)
GridViewAllClients.SelectedIndex = SelectedRowIndex
GridViewAllClients.DataBind()