iOS appears to only randomise the MAC address on boot, Android 8 (Oreo) and 9 (Pie) are still relatively new, prior to Pie manufacturers had to enable the functionality, it appears like with Pie this happens automatically. You can see from the Android docs this started with v6 https://developer.android.com/about/versions/marshmallow/android-6.0-changes#behavior-hardware-id it clearly states
When a device running Android 6.0 (API level 23) initiates a background Wi-Fi or Bluetooth scan, the operation is visible to external devices as originating from a randomized MAC address.
This obviously does not affect every Android device out there, because Android being what it is - some devices probably have the feature disabled by manufacturers, but some devices will have this feature turned on and it would explain why people above are reporting multiple non existent MAC addresses being reported.
It is worth noting however, that LE Privacy is a core part of the Bluetooth v4 spec, and as such while it may well work great right now (for some people), going forward more and more devices will report a different random MAC address when probing for devices.