I noticed similar differences between the following two devices:

• Wiko JERRY smartphone (Android 6.0.?) seemed to need pairing, it accepted the PIN “00000000”, but even then it didn’t connect properly in abt. 49 of 50 cases or so. In other words: it worked almost never.
• NEXUS 7 (2013) tablet (Android 6.0.x) is always connecting reliably and flawlessly – without explicit pairing.

(As I could always switch to the tablet, the not-working phone wasn’t a big problem for me, so I didn’t mention it here until now. But the problem existed from the beginning, that is, since october when I got my mooshimeter.)

Some weird details with the problematic JERRY phone (and possibly other devices with similar behavior) may be of interest for you, @James:

I discovered a different behavior after the recent app update to version 1.0.34 (2115). At my very first attempt with the updated app, it surprisingly connected without problems, but I was “forced” to do a firmware update, although it reported the same version numbers (1477971088) for both the currently installed and the offered “new” firmware. Somewhat perplexed, I agreed to make the “update” – and wasn’t bothered again afterwards. Since then, the BLE connection appeared to be very robust – it connected always without problems and sometimes even without pairing.

But the joy didn’t last long – after the next reboot of the phone all the old connection problems were back. :-(

After this disappointment, I tend to assume that spurious effects – and not the app update itself – caused the connection to work temporarily. At least, it’s now proven that it CAN work reliably, but seems that this is depending on some kind of unknown “statefulness”. Seems almost impossible to find the concrete flaw…