The search tool for relationships has some conflicting behaviors related to the fuzziness rules.
Ex. 1: If you enter "The ACME " and select "The ACME Company" from the popup list, the search results are fuzzy on each term – i.e. all orgs with "The" OR "ACME" OR "Company" in the list. The word "The" is common enough this yields a "too many in search results" message.
Ex. 2: If you enter "ACME" in the search box, it yields no results, because it apparently does not provide a fuzzy wildcard at the beginning of the string.
Ex. 3: If you enter "%ACME%" you've now controlled the fuzziness, so you retrieve a usable list.
In 2.1 sandbox, the search popup behavior is modified so that selecting a record from the popup list directs to that specific record (which is great). But there may be need for adjusting the fuzziness rules some more, as not selecting from the list (searching on a partial string) may still yield awkward results.
I tried testing further on 2.1 sandbox but there appears to be some bugs with that search tool (try entering "company" in the search box – yields all orgs in resultset).