I spent the last couple of days designing a web service API. Last time I did that was more than six months ago, so I forgot a lot of little tricks and gotchas which I had to relearn. To save you some trouble, here are some notes:
Currently, Visual Studio .NET is the best environment to start in for web service design. So I started a Web Service project in VS.NET 2003, wrote my API classes in C#, and launched the service to get WSDL. I also wrote a .NET client to polish the API. BTW, VS.NET generates doc/lit style web service which is usually what you want.
I used only simple datatypes to avoid interop issues later. Complex datatypes should be used only if the benefits are clear because most binding generators will map them to classes which have to be instantiated on both side.
You might want to go easy on the Enums too because VS.NET uses enum symbol names as string literals. I dislike verbose XML, so I used simple character flags (similar to fopen mode flags) instead as a compromise between fully descriptive strings and bit flags although I used strings to represent the flags for extensibility.
Interop by Passage
Now that I had a WSDL, I fed it to Apache Axis's WSDL2Java tool to generate Java bindings. I ran into several interop issues with Axis 1.1 so I ended up using Axis 1.2beta2 after a few hours of agony. Since the service I was designing will be implemented in Java, I generated server-side bindings first and hosted them in Tomcat.
Once the Axis-based service was running, I added a Web Reference to it in my C# client and made sure results from the Axis-based service matched the .NET-based service. Note that at this point, you have two WSDL, one from each side. You'll eventually have to let one of them go depending on where the service will be hosted in a Java web server or ASP.NET, but it's nice to have both for developing clients in other languages.
At this point, it's smooth sailing as far as interop is concerned.