I believe some Android phones (at least, the Galaxy Nexus and Droid X) randomly select a new MAC address on reboot. Whether this is a bug or a feature depends on your point of view:

* Android Issue 23330: Galaxy Nexus (VZW/LTE) wifi MAC address changes with every reboot https://code.google.com/p/android/issues/detail?id=23330

* Droid X WiFi MAC address changes when I power WiFi on and off. http://rootzwiki.com/topic/1332-wifi-mac-address-changes-whe...