I just resolved this using the following steps (these are the raw troubleshooting steps, not sure which one worked)
- Open the hood and remove the positive cable of the battery (red one) and leave it off for approx. 30 minutes.
- Reconnect the cable to the battery and start the car, that will reset the system.
- Connect another device to your Mazda Bluetooth first.
- Just in case, do a network reset on your Mi A2 Lite (Settings -> Search for reset -> select the network reset option)
- Connect a headphone or a similar device via Bluetooth to your Mi A2 Lite and leave it paired and connected.
- Go back to your Mazda, try to pair again and wait until the count down hits 130 sec left, your phone will find your Mazda Bluetooth by then.
I'm not sure which step(s) resolved the issue but following the above steps will reset both your ECU on your vehicle and your phone's network configuration back to default.
Hopefully that works for anyone else who has this issue as well, since it worked for me.
- Aria