Comment 14 for bug 1699660

IIRC what could be happening is that the additional timeout introduced by systemd-resolved first doing the newly implemented LLMNR lookup (which fails if not implemented by any device) causes some network tools to not even try doing a DNS lookup using the DHCP- or user-supplied DNS search domain suffixes.

The second invocation then maybe finds a cached result which is however invalidated after some time - thus the varying or seemingly random results.