I know this is an old post but just found it as I'm having the same problem and wanted to know if there was a fix and seeing as no one has answered your question, I will...
Its Samsung Galaxy phones that are the problem, my S8+ phones, S7 Edge and S6 and Note8 are the only ones having this problem and from looking on forums, it seems to be a very common problem with the Galaxy line.
Just to confirm I have had this problem on all the latest stock OS's and have even factory reset countless times to try an fix it, currently on the latest Oreo update on the S8+ and it's still got the problem but my Google Pixel 2XL, HTC U11 and even an old Lenovo Zuk Z2 Pro from 2016 that had to have Google play apps/services side-loaded (as doesn't come with them as stock) doesn't have this problem and its infuriating...
Thanks Samsung, due to this, your slow pushing of updates (something even the Zuk released Oreo before you an they are problem 1/1000th of your size) and your now minimal improvements to your next gen phones and your price battle with the idiots at Apple I will be switching to HTC or Google as my only phones from now on...