What is a service?

I see a lot of material about SOA but not much thought has been given to what exactly is a service. SOA puts a lot of emphasis on the infrastrutucre which makes development and usage of services possible. But how does one define (useful) services? What must be its granualrity? Is it really possible to have stateless services in a typical enterprise scenario(barring text book credit check service)? What I mean by real stateless service is that a service may have a clean input output specification, but can it be performed out of context? If not, who sets up the right context? Possibly another service? Where, then, this dependency specified in service specification, if services are self contained?

Let me give an example.
In insurance world a cusotmer is given a proposal based on his/her requirements. And when proposal is accepted and premium paid, it becomes a in-force policy. Now if I have a service which accepts propsal and payment details as input and returns in-force policy identifier as output, do I have a valid service?
This service cannot be performed unless a proposal was made, which might have required execution of some other service. So how do I add this dependency in my service specification?

Now somebody might say, that this is mere choreography of services. I would argue otherwise. Choreography of services is possible, if they can be choreographed together. Where do I specifiy this choreographical compatibility?

A more general question I would like to raise is that if services are explicit contract between provider and consumer then just specifiying input, outpt and exceptions sufficient to describe the cobtract fully? Shouldn't we add context in which this contract is valid? How do we specify this context?

The reason I am so woried about it is because, the great promise of SOA is promise of service as means of integration in a large enterprise. In a large enterprise there are sufficient challenges to get the data definitions to be compatible and right. But even after getting data definitions right, services may not fulfill the promises becuase they also need right context. Consumer cannot be sure of using a service, if he/she does not know what context the service executes in. This will result in cloning and re-implementation of services rather than re-use. Soon there will be proliferation of services and they will become as unmanageable as point to point interfaces.

Incidentally I feel this is the reason, in first place, why people create point to point interfaces.