How is this handled in GrapheneOS @Final ?

Exactly

Yeah, that's what I assume. Setting up a phone requires government issued ID. You could use an older second hand phone, like 2012 or older, and only use public wifi networks to connect to the internet. But I'm sure they'd still be able to track who is who.

I'd be very surprised and disappointed if @GrapheneOS was also guilty of this. It's pretty fundamental to privacy.

There is no true anonymity

I think advertising IDs are even more nefarious and hidden and persistent than the operating system IDs

The only solution is to never use an electronic device. At all. Ever. Unless you build it yourself from raw materials, or it is habd-rolled analog goodness. But even then, the uniqueness of something like that makes it easy to pick out.

I use for VPNs is for safety on open access WiFi networks, or circumventing geoip based restrictions. Also accessing private networks. Privacy-wise they only protect you from ISP tracking. For the rest there's browser fingerprinting too, and using linux makes you stick out in that respect. So use several browsers on Linux, and for anything truly private, e.g. anonymously contributing to freedom software, use a dedicated linux VM + Tor and may be VPN too. Do absolutely nothing else from that VM. Ideally enforce that in code or iptables as you will slip.

Linux has unique identifiers, too

What is the software that links the npub to the devices ID and reports it to Microsoft/Apple/Google or whomever?

GrapheneOS does not create identifiers for users nor track them. All services we do host require the minimum for that service to function, for example when requesting an OS update we would only be able to see an IP address checking an update for a certain phone model. Android has an "Advertising ID" but this is Play Services dependent and can be deleted in their settings.