I don't know if all Android version do this by default, the one on my phone does: Whenever it connects to an AP, it generates a new random Fake-MAC. So, it's not a per-SSID permanent MAC, but a new one on each reconnect.
Now, at Bahrein Airport the WiFi coverage is somewhat spotty. Due to this you have lots of devices reconnecting. And each time they register with a new MAC.
The DHCP server behind their WiFi has a least time of 14 days. And even with them having chosen a /16 IP range for their DHCP, at an airport you can already imagine that those limits are not clever.
And even worse: The system is self-DDoS'ing. This is because every time a phone connects, and the DHCP server has run out of IPs, after a couple of seconds the phone will disconnect, and then try to reconnect - with ANOTHER random MAC address.
The solution I used myself (and showed to a couple of other people in the lounge was) was disabling the privacy feature. This way your MAC would stay the same. You then would keep hammering the AP until one of the thousands of leases had timed out and a IP was available again. You'd then get this IP, and due to your MAC staying constant having reconnects to it (for example because you went to the toilet) also aren't a problem.
So, let this be a lesson to those administrating large public WiFis: Now that devices use random MAC addresses, consider to make your DHCP pool larger, and the lease time much shorter. Unless you are Tom Hanks, you would not typically stay 14 days in an airport terminal. :)