This is very similar to our earlier work on the security of MAC address randomization: http://papers.mathyvanhoef.com/asiaccs2016.pdf They provide some more practical details if you want to implement our probe request fingerprint tracking mechanism. This is a passive tracking technique.

Their method to track all devices requires actively sending packets for every single MAC address that is being tracked. The (imperfect) passive tracking techniques can be used to reduce the number of MAC addresses you have to try though. Nice finding overall! And it will likely be hard to patch this issue..

Sometimes there are also silly driver bugs that allow you to get the real MAC address of a device when the user is using a spoofed MAC address :) http://www.mathyvanhoef.com/2013/11/unmasking-spoofed-mac-address.html