So the problem you've identified is real. I used to have some bootleg footage of some private amazon tech talks where the speaker emphasized that in distributed systems it was generally a terrible idea to have transactions span entities.
I think you basically have to learn to live in an eventually consistent world. In the case of people being deleted I would imagine that the user service exposes a pub/sub interface where address and billing services subscribe to "delete" events.
Hardly need "private bootleg" footage to discover this reality. Pat Helland (at the time, working at Amazon) wrote a paper about it maybe 10 years ago.
You don't HAVE to live in an eventually consistent world. If you use something like ZeroMQ or use REST then you can "notify" other services of a "person deleted" event in a synchronous manner.
That has nothing to do with the fact that if your systems are distributed, you will have eventual consistency.
If System A needs to tell System B about an event in order for A and B to remain consistent, but B is down, you've got eventual consistency, because B can't become consistent with A until it's back up and has performed whatever recovery is necessary to process that event. Service discovery does nothing to solve that problem.
In addition, the network isn't just up or down. It's varying shades (dare I say, 50 shades?) of down or broken. A single machine might not be accessible due to a switch issue. An entire rack or aisle might be compromised by a bad router or faulty routing table. A network cable might be flaky. The truth is you just don't know, and that's all inside a single LAN.
Your service discovery system could be able to see service {A,B,C}, but service A can't talk to B or C due to network issues. It happens.
I think you basically have to learn to live in an eventually consistent world. In the case of people being deleted I would imagine that the user service exposes a pub/sub interface where address and billing services subscribe to "delete" events.