When adding the service reference try clicking on the ‘Advanced…’ button and then uncheck the ‘Reuse types in referenced assemblies’ checkbox.
I found this out when I had created a simple project to test a third party service which all worked fine. Attempting to add the same reference to the main project resulted in the app.config and reference.vb file not being generated correctly.
I think this may have been because there were already other web references in the application or referenced applications, however unchecking ‘Reuse types’ resulted in the files being generated correctly.