There are 2 different sources of this issue:
1. The main source is that User Status and/or System Status are selected as searchable columns by default. This has been reported as a bug, VSTS #65506.
The work around is deselect both User Status and System Status when searching. Alternatively, the Administrator may update the configurations using the Admin Client to make the User Status and System Status as not searchable.
2. The search in Notifications and Maintenance Order configurations has been found to be case sensitive despite the APM database being case insensitive. This has been reported as a bug, VSTS #65539.
The workaround is to ensure proper case is used when searching on these specific tabs.