In one embodiment, a service maintains a database of media access control (MAC) addresses of devices in a network and their associated telemetry data captured from the network. The service identifies a new MAC address being used by a particular device in the network. The service matches telemetry data associated with the new MAC address with telemetry data in the database associated with another MAC address, by using the telemetry data associated with the new MAC address as input to a machine learning-based classifier. The service determines, based on the matching, that the MAC address in the database associated with the matched telemetry data has been updated to the new MAC address by the particular device.