I'll probably forget to check when I get home. Does anyone know if Android randomizes the MAC address on every disconnect/connect with the random MAC option enabled?
Not by default. It remembers the MAC for each specific network. This is because sometimes you want to have specific device on the same IP all the time. The DHCP decides this via the MAC.
If you want it truly randomised every time you need to turn on non persistent MAC randomisation in the developer option.