Прежде всего, вам нужно использовать локальный IIS, а не сервер разработки ASP.NET, что является хорошей привычкой. После этого убедитесь, что у вас есть анонимное разрешение с новым веб-приложением.
Во-вторых, добавьте веб-сервис в качестве справочника услуг.
В-третьих, я использовал этот фрагмент для тестирования веб-службы при следующих обстоятельствах:
Private Sub cmdSearch_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdSearch.Click
Dim ws As New ServiceReferenceName.WebMethodsSoapClient()
Dim bs As New BindingSource()
bs.DataSource = ws.NAmeofMethodinWebService(txtSearchCriteria.Text)
DataGrid1.DataSource = bs
DataGrid1.Visible = True
End Sub