The implementation of Search, Lookup Filters and unseelctive search terms was the root cause. This is the answer we got from Support:
An entity-specific search (e.g. Case, Account, Custom Object) will
return at most 250 results. Lookup Filters will then only apply to the
top 200 search results. This filtering is performed post-query as it
relies on information present in the database but not in the search
index. As a result of this, if the desired result does not appear
within the top 200 search results, it will not appear in the Filtered
Lookup list. This means that the combination of a high-hit-count
search (e.g. a search for “Sales*” that returns a thousand results)
and a Lookup Filter can cause many “expected” results which are
retrievable through more restrictive queries to not show up when using
the Lookup search.
Suppose in your org has over 10,000 records that start with the word
"Spanish". A search for "sp" returns a max of 250 records and then the
Lookup Filters evaluate those results according to the filter
criteria. If the 250 records returned in the initial query do not meet
the criteria of the Lookup Filters, the lookup search will return 0
results and make it appear as though it is not working as expected
even though it is.
Workaround: Either remove the Lookup Filters, make the Lookup Filters
less restrictive or use more restrictive search terms.
This is also documented in this Knowledge Article.
That was exactely our case. In a specific customer org (not in any of our dev orgs) we have thousands
Period__c records with a text Year field of value "2020".
Period__c records are tied to the
Contract__c by using a Lookup filter.
If non of the first 200 returned
Period__c records "belongs" to the current
Contract__c parent record We get ZERO results.
We think this implementation is absolutely suboptimal and strongly reduces the use cases for Enhanced Lookups. Maybe we or someone else will create an IdeaExchange for that.