Wi-Fi Privacy Police is an Android app that solves this problem by disabling these kinds of probe requests. It's open source with extensive documentation to boot.

https://github.com/BramBonne/privacypolice