Why do phones send wifi probes?

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.