Had a long chat and telephone call and remote session with Apple support today. None of the guys could do anything to solve this issue. They recommended to restore the iPhone from an iCloud backup instead from a locally stored backup, as there are some settings (they might cause this issue) not included in the iCloud backup.
Before restoring the iPhone they said I should set it up as new and first check if all is working fine and the messages app has permission to read the focus status, then in the next step I shall restore from iCloud backup.
I asked them for a profile they could send me which cleans up or resets all app permissions (not only location permissions), but they stated that they don't have such a profile.
Sounds clueless. Setting up as new and restoring is a long process with all banking apps, Apple pay cards, Apple Watch etc., so I will wait until 15.1 comes out. If I still have this problem after that, I might set it up as new.
Just wanted to let you know.