Searching for Nickname not working reliably

Nextcloud version: 19.0.4
Operating system and version: Debian 10.6
Apache or nginx version : Apache/2.4.38
PHP version : 7.3

The issue you are facing:

Nicknames are not found on most entries, only on those that lately have been viewed.

Is this the first time you’ve seen this error? (Y/N): No

Steps to replicate it:

  1. Define some contacts with nicknames
  2. search for one -> no result
  3. search for his real name
  4. change the view
  5. search again for the nickname -> get an result
  6. reload page
  7. search again -> no result

It looks like the nickname is only cached in the browser but not really searched on the server-side.