The MAC address is stable once a device is authenticated (connected) to the network. With the trend of providing 'free' wifi access within stores, making sure that users connect to that network is enough to continue tracking them.
That is necessary to keep the gateway from having to issue a thousand ARP requests (one for every packet you send from a different MAC), but there is no reason why the MAC chosen to connect to the network couldn't change every time you disconnect and reconnect. That would at least prevent you from being tracked between visits to the store [using this tracking method], even if you actually use the network.
I can narrow down a huge list to a very short list using above information along with the probes being sent out co-related to the signal strength. Timing of each probe can also be leveraged in uniquely identifying,most probes are sent in interval from each device. Those probes that come in equal intervals are likely from the same source, leveraged against signal strength you can likely identify a small crowd. To take it even further you can calculate the signal as absorbed through the store to signal congestion and possibly other metrics.
Even by sticking to a certain subsets of OUIs, it's still probably fine. On top of that, listening to traffic (even after picking an in-use MAC) would allow you to determine if someone else is using that address.
But still, I agree, it would be very hard to have everyone connect to your wifi.