The dropdown in linked records fields by default only loads the first 100 records initially. Typing in the record finder searches matching records beyond the initial results. The finder’s filters and record-access restrictions still apply.
You can provide guidance to your users by explaining in the field’s description that they can find a record by typing its name in the search box.