You can kinda fix this by lowering the ndots value. But probably the better way to fix this is to not include a 'search' directive at all. Don't specify anything for 'search' or 'ndots'. And then do as you say, use FQDNs everywhere.
Using a FQDN (as in, a DNS name with the trailing dot) is the only reliable way to avoid this without breaking other things!