Reminder for my question:
"Is this Bluetooth LE using new security settings that Android 7.0 is unable to validate?".
It seems like some Android-devices are able to discover the right services, but other devices too only have the service with the above UUID...
I don't know specifically what changes to their BLE stack Android 7.0 might have made to cause an issue like that, but every major version of Android seems to break a lot of BLE app functions. Sadly that is the frustrating world of Android development. Let us know if you figure out what the cause is so any other users seeing the same issue can benefit!
Seems like the problem is due to permissions. Android 7.0 doesn't only require Bluetooth-permissions but also Location-permissions (AccessCoarseLocation and AccessFineLocation)...
Stupid permissions had me searching for days! Thank anyway!