I would have not have thought an unreachable host was exceptional, given that it's quite normal.
The point is that handling the host unreachable is almost always semantically higher level than the code opening the connection. This the code opening doesn’t implement the policy of what to do when the situation occurs. In the case, say, of a hard-coded address then it’s possible the author of that piece of code does know how to handle a host unreachable case.
On the software abstraction, exceptions are simply a convenient implicit control flow device for handling the alternate path when an intended state cannot be achieved. I don't follow the paper's argument that "current exception design is suboptimal for efficient implementation" - but I would not be surprised considering the lifetime issues.
The argument of the paper is really that exception handling shouldn’t use a global lock, a problem made worse by the proliferation of processor cores on modern chips.
So if you are trying to hold a lock you don't throw an exception, you just wait and try again. Perhaps you can't reach that host; try again a few tiles before giving up and throwing an exception. But if you try to write to removable media and the device won't open, all, your program isn't going to mount a tape itself: throw an exception and let the problem be handled at a higher level.