After talking to a lot of people, I am trying to cement the relationship of policy to the contract. There is a thought that policy is part of the contract. That policy is created up front and negotiated between the two parties alongside the rest of the contract (i.e. WSDL).
Others have aligned themselves better with the four tenets of SOA. That the notion that "Services share schema and contract (not implementation)" is core to "Contract-first" development and that policy is negotiated between the services (perhaps afterwards) as stated by the fourth tenet, "Service compatibilitiy is negotiated through policies".
One comment I liked about policy was in the OASIS SOA RM spec is, "Whereas a policy is associated with the point of view of individual participants, a contract represents an agreement between two or more participants.".
Does this mean that the policy at some point may become part of the contract?
The way that I think about the problem is that there are several levels to Contract-first Design.
Level 1 - Functional
At this level, participants negotiate the functionality of the Web service. They describe the syntax of the interaction (schema&messages) and the semantics.
As WSDL is really just an IDL, today the semantics are described out of band in a non-standard manner, except in the few situations where the WSDL has been extended. One way is to use policy assertions to assert the business rules of service interaction.
Policy, however, has not really been used widely in this manner today. I would love to hear from you if you use policy in this way.
Level 2 - Non-Functional
Policy can also be used to assert non-functional aspects of a contract such as security, reliable messaging, transactions, etc. This is what most people in the industry think of when they think of policy.
While some think of this up front, I do not expect that this is as common as negotiating the form of the WSDL prior to implementation. Nor is it as asked for.
Thereore, to prioritize, I would definitely think that in the short-term WSDL first is what pops to mind when people say "Contract-first" development. In the long run, "Contract-first" will really incompass more than just the WSDL.