I've seen many of consent forms mention tracking beyond cookies and cross-devices.

Are you sure that by accepting you aren't just accepting legally to continue to be tracked with all other means?

If true, then deleting cookies only cause them to ask again next time, but you're still fully tracked.

See https://www.kompyte.com/blog/5-ways-to-identify-your-users-w... (just found it) for examples of tracking without cookies.

More like "they had, but decided to remove". Firefox on Android used to support any extensions, but they cut that down. You can still get the functionality in browsers like Icecatmobile, though.