Traditional big web services, like a billing system or a service running in the cloud, nearly always have fixed addresses--often HTTP URLs. Smaller web services, such as those on a PC or a device, often have logical identifiers ("urn:uuid:c3de740f-9227-4706-b3ee-9494243c040d") that let you recognize the service, but which don't actually tell you anything about how to contact the service.
One of the great uses of WS-Discovery is transforming logical addresses into physical addresses (e.g., http://my_pc/service/) so you can actually contact the service. A service uses the xAddrs field in WS-Discovery messages to express its transport addresses.
But it turns out that these xAddrs are optional. There are actually a lot of really good cases why you would want to omit them--if they're very large, or if you don't want to generate different Hello messages for every IP address in the system--but the specification doesn't clearly explain when they're often omitted in the real world, and what happens when they are.
So let's go through the four messages a service can send.
One interesting consequence of this is that the example sequence on page 11 of WS-Discovery (Probe -> ProbeMatches -> Resolve -> Resolve Matches -> success!) almost never happens. Services usually include xAddrs in their ProbeMatches messages in the first place.