"a) The network is not hostile and allows access just fine, but..."
This came up before didn't it. Nick mentioned that the question `network down` isn't the easiest question to answer portably. Supposing such a network could have it's properties (like route) enumerated this might provide another solution to (a). If the network changes in some measurable way without also being immediately preceded by a bootstrap (route shows next hop unreachable), then consider the network down and schedule attempts to reestablish communication.
A key problem will be distinguishing this type of network from a hostile network where the access is just cut off. Most likely to force a bootstrap, or guard-rotation like activity. A warning here to indicate the network was bootstrapped, but for some past interval(s) the network appears down (and should the client check firewall, gateway, or try a bridge). A client should probably be `aware` of some level of network access, otherwise all solutions are naive.
"b) ..."
Retrying guards is the crux of the problem. If you blindly retry guards, even to prevent rotation, you eventually come to a hard place where this will backfire badly. Even if it works sometimes. Although I don't think the client should rely on the OS (which may be compromised).
--leeroy