Modern IOS versions randomize the MAC used for passive wifi scans. I'd imagine android is also doing the same.
Its been said that this is how they have changed IOS 8, however
I've only noticed that they have decreased the number of beacons it sends greatly;
the same MAC is used for the probes; and given the ability to profile devices passivly [pdf],
the MAC may not be the only thing to worry about.
If you have a wireless card that can go into monitor (radio promisc) mode,
you can see all of the probes constantly travelling around us:
tshark -i mon0 -R 'wlan.fc.type_subtype eq 4' -T fields -e wlan.sa -e wlan_mgt.ssid -e radiotap.dbm_antsignal -e frame.time -E separator=, -E quote=d
Thing is the penetration of these monitoring techniques is difficult to
ascertain, I've been looking for them when I visit big retailers, but
according to people like Glenn Wilkinson and Brendan O'Connar,
these may be fairly easy to setup and in wide use surreptitiously.
(Authors of Snoopy and CreepyDOL)