Here is the MAC Randomization described and stated:
Note: Randomized MAC addresses are generated per SSID and are persistent.
I can confirm after deleting the SSID, rebooting, and connecting again, the same random MAC is used as before. However, if you reset the device to factory defaults and connect to the same SSID, the device connects with another random MAC address.
So how can you trigger this behavior without doing a factory reset?
On Android 11, there is a new option "Wi-Fi-enhanced MAC randomization" in the developer options.
When you enable it, delete/forget the network, and then reconnect, you get a new MAC address every time. Also, you get a new MAC address for this WiFi/SSID when you reboot your device. Disabling and enabling WiFi is not enough to get a new MAC. With this enabled, the device also generates a new random MAC address every few days.
When you disable this option, you get back your previously used random MAC.
Please also read liangpig1's answer, which is very informative.
Even with a new random MAC, some WiFi hotspots recognize you and still show your free hotspot time is over. This seems to be because of cookies with the Android browser. To mitigate this: connect, dismiss the notification that you have to log in, and in your browser in a new private window, open any non-HTTPS website. Then you'll be redirected to the login page, can log in, and enjoy free WiFi again.
The key related to MAC randomization is only generated for the first time.
And the MAC address is calculated by calling hmac_sha256 over the SSID with the generated key.
This key is stored in the /data/... on the device, and as far as I know, Android does not provide any API to remove it.
But when you perform a factory reset, all the data located under /data/... is wiped out, that's why the MAC address changes after that.
Therefore, if you can manage to remove the key, you can trigger this behavior, which is not easy, in my opinion.
Here is a list of events that will change your random MAC:
