A network health management service (NHMS) component associated with a virtualized computing service receives network health updates from a first encapsulation protocol processing component (EPPC). The health updates are based on traffic observed between the first EPPC and another EPPC. The NHMS component obtains additional metrics to diagnose a potential network impairment indicated by the health updates, and initiates remedial actions if the additional metrics appear to confirm a network impairment.