After lots of frustration, as depicted in Search in DTTG is broken? I finally found the problem!
If you disable Spotlight in the settings before syncing a database from a remote location, it’s tags are visible in the list of tags, but are not available in a search for tags!
The only way to get them then available in a search, is to re-enable spotlight!
This is easily reproduced and stays true for the next database that is synced from a remote location.
I did not yet test how newly added tags are handled and if they are properly synced to remote and to other devices if Spotlight is disabled after the initial sync.
PLEASE check this in detail and fix, as I really do not want to store my most private information in Apple Spotlight, which I avoid like the plague.
Many many thanks