Is Web Services interop possible? Absolutely. Is it easy? It depends on how you define interop. The term interop is sufficiently vague that it warrants a definition. I define interop as:
A client and service written in different languages successfully communicating data.
If you think this definition is too simple, maybe I don't expect as much as you do. My view is that this definition is the minimum acceptable level of interop; anything beyond this is nice to have but not required. But there are other views on the meaning of interop.
Most developers expect interop between their Web service development tools. As a VB developer, you might expect that VS .NET should be able to add a Web reference to a Java service and auto-generate ...