Can't resolve hostname.local on LAN

I used to be able to ssh user@hostname.local between machines on my LAN but it is no longer working. I can ssh using the IP of course, but it's DHCP so it may change from time to time. Both machines run Debian 9.12, one is a VM in a Windows host, but still, it DID work ; I haven't fooled around with the config files, just regular updates.

ping hostname.local
ping: hostname.local: Name or service not known

(it might not be exactly that message as I translate from French)

ssh hostname.local
ssh: Could not resolve hostname hostname.local: Name or service not known

(ssh outputs in English) From avahi.org : > Avahi is a system which facilitates service discovery on a local network via the mDNS/DNS-SD protocol suite I've looked into /etc/resolv.conf, /etc/avahi/avahi-daemon.conf, /etc/nsswitch.conf but it's standard out-of-the-box config. /etc/resolv.conf (reset by network-manager each time it starts)

# Generated by NetworkManager
search lan
nameserver xx.xx.xx.xx # DNS IPs obtained from DHCP
nameserver xx.xx.xx.xx

man resolv.conf says that the search list contains only the local domain name by default (something like that, I translated from man page in French) ; shouldn't it be localinstead of lan ? I tried to change it and ping or ssh another host on my lan right away (without restarting network-manager), it didn't work. And when I restart network-manager, it rewrites /etc/resolv.conf and sets search lan. /etc/nsswitch.conf (default, I haven't made any change)

# /etc/nsswitch.conf
#
# Example configuration of GNU Name Service Switch functionality.
# If you have the glibc-doc-reference' and info' packages installed, try:
# `info libc "Name Service Switch"' for information about this file.

passwd:         compat
group:          compat
shadow:         compat
gshadow:        files

hosts:          files mdns4_minimal [NOTFOUND=return] dns myhostname
networks:       files

protocols:      db files
services:       db files
ethers:         db files
rpc:            db files

netgroup:       nis

I've tried to discover hosts and services with avahi-browse and nbtscan, which rely on avahi (zeroconf / Bonjour), but they seem to find only the host on which they run. (I know this is a possible duplicate of other questions, but I didn't find any answer and I don't have enough reputation to do anything)