Unless it makes use of MAC randomization, they can track it.

I’d also add that I’d be far from sure that even devices that are randomizing them are using a cryptographically-secure PRNG and reliable source of entropy to seed that PRNG. Even much-more-expensive and capable-of-obtaining-entropy personal computers with software that can be more-readily-inspected have had a spotty record of using solid randomization. I’d give pretty good odds that there are devices out there using a fixed seed and non-cryptographically-secure PRNG for MAC randomization, and that someone like Google, with a vast database of MAC/time/location data and a bunch of smart computer scientists on staff, could probably break the randomization if it wanted on at least some devices.

But you gotta crawl before you can walk, and today, we know that we aren’t even crawling.