Here is a list of top 10 rules that ensures if a Web Service is a true Web Service.
A Web Service should expose its service contract using WSDL. If it can't give you a WSDL document, it's probably just XML over HTTP.
All messages sent from and received by the Web Service must use SOAP formatting. If it's not using SOAP it's probably just XML over HTTP.
All data types in the SOAP payload must be XSD compliant. No platform native types are allowed. If it's not using XSD it's probably just XML over HTTP.
The underlying messages should of course be formatted using XML.
No Arbitrary Binary Data
The message payload should 7 bit ASCII and should contain no embedded binary blobs. Any binary data passed over a Web Service should be sent using either SwA, DIME or MTOM (preferably MTOM).
Transport is likely to be HTTP
Although not a requirement, the majority of Web Services today use HTTP as the transport. Compliant Web Services should definitely work over HTTP.
Discovery can be through UDDI
Again although not a requirement, it should be possible to host the Web Service endpoint using UDDI.
Agreed Versions of Specifications
The versions of the above specifications (WSDL, SOAP, XSD, XML, HTTP, UDDI) should be in line with the latest version of the WS-I Basic Profile (http://www.ws-i.org/) - to ensure Web Service compliance between vendors.
Operations should be Document Style
Operations to/from a Web Service should be Document/Message Style (e.g. SendOrder(order o)). RPC style should be avoided (e.g. SetOrderLine1(orderId id)).
Should be compliant with WS-*
Compliant Web Services should be able to accept WS-* payloads and extensions for Security, Reliability and Transactions (although not all stacks today support these yet)