A first encapsulation protocol processing component (EPPC) at a particular device of a virtualized computing service establishes a network packet tracking session with a second EPPC at another device. The first EPPC tags at least some encapsulation packets (which contain baseline packets generated at or directed to guest virtual machines) sent to the second EPPC as tracked packets. The first EPPC obtains network metrics corresponding to the tracked packets of the session from the second EPPC, prepares network health updates based on the metrics, and send the updates to a network health management service associated with the virtualized computing service.