gUM is designed to recognize deviceIds an app may have stored in cookies or localStorage, so once both cookies and storage have been cleared, the reason to keep track of them is gone (and they can be rotated).

We already have language on deviceId:

Since deviceId may persist across browsing sessions and to reduce its potential as a fingerprinting mechanism, deviceId is to be treated as other persistent storage mechanisms such as cookies [COOKIES], in that User Agents MUST NOT persist device identifiers for sites that are blocked from using cookies, and User Agents MUST rotate per-origin device identifiers when other persistent storage are cleared.

So the question is if "other persistent storage are cleared" covers the Clear-Site-Data header. If it does, it's an implementation bug.

I don't think "other persistent storage are cleared" has a precise definition, which is part of what we need to address.

I guess we could either refer to https://w3c.github.io/webappsec-clear-site-data/#abstract-opdef-clear-dom-accessible-storage-for-origin et al.
Or we could define a data type and a hook in the spec to clear that data type
https://w3c.github.io/webappsec-clear-site-data/ would then call this hook when any of the other data type is cleared.

See also #675

FWIW, Chrome is implementing rotating device IDs with Clear-Site-Data: cookies.