While doing my random walk I found this recent post by Aaron Skonnard. Good topical commentary around the issue of "WSDL First" design, and the challenges people experience with it.
The problem addressed in that post - if you do WSDL First, you don't get to play with your domain-specific types, which probably already exist! Web services is thus a non-starter.
Skonnard describes a practical approach to interop, which I have been promoting for a long while now: iterate with a code generator tool, either designing XSD or WSDL directly (which implies XSD), to create the immutable types that get used to represent messages on either end of the wire, whether those ends be implemented in Java, C#, PHP, or something else.
Then, create transformation logic that can create your domain-specific types from that wire message, or vice versa. You might consider using the Memento pattern for this job.