They could just listen to beacons. Why do they probe for every network you've ever connected to?
Do other wireless devices do this? Does Windows, Linux esp. Kali, do this?
That is because listening for a beacon and not getting it just might mean that the network has a private ("hidden") SSID. From this article (emphasis mine):
The 802.11 standard allows APs to beacon with the SSID field set to null - this is referred to as a hidden SSID. A client that wishes to associate with an AP using a hidden SSID must first send out a Probe Request that contains the SSID of that network, which will then cause the AP to provide a Probe Response. For any client that does not provide the correct SSID, the AP does not respond.
I believe that probing can be deactivated in Linux; not sure about Windows, but given their history I'd wager that probing is on by default, and may perhaps be disabled through some obscure registry hack.
Another reason is asymmetry - if you see the AP does not mean the AP sees you. Successful active scan guarantees that you can connect to the AP.