I can think of several ways that this message can be produced repeatedly:
You have turned off the StrictHostKeyChecking option in ssh on the client and the guest has been reinstalled, or has reinstalled its ssh server. When an ssh server package is installed it generates a new fingerprint and installs it in /etc/ssh. Note that newer versions off ssh hash the hostnames/addresses.
If you were connecting to a new guest (at a new IP or name), or an old guest but at a new IP or name. While Kamil is using a bridged network, this problem can occur when default networking is used as the ssh command for various guests is directed to the host computer. The same is true for guests behind a NAT firewall where the source of the ssh is on the other side of the firewall. The solution is to use the hostkeyalias function of the client's ssh configuration files.
Something is deleting or modifying your ~/.ssh/known_hosts file in the account from which you are initiating ssh.
So either the guest fingerprints are changing or there is a change in the mapping of guest->name->IP address, or the account you are ssh'ing from is forgetting their fingerprints.
If you connect to the same guest twice in a row seconds apart and the The authenticity of host 'samename.local (same ip adress)' can't be established.
ECDSA key fingerprint is xx:yy: ... message changes the fingerprint, and you can confirm that you reached the same guest by examining its contents (not by MAC address), you know the guest is changing its fingerprint. You should be able to confirm this by examining the times is
ls -l of the guests /etc/ssh directory. If you were rebooting in between, and if it were from a CD (it's not) or an installation USB key or installation USB key image this would be understandable. You don't mention having to reboot these guests to get the error, either. So this possibility seems improbable.
If you can see that entering the same ssh command gets you to a new guest by examining the contents of the guest you know you have a problem in name->ip->guest mapping. There's lots to go wrong here.
If you see the same actual fingerprint over and over and see that the IP and name of the guest haven't changed you have a problem with your ssh client machine erasing all or part of the .ssh/known_host file. You can confirm that with the times in
ls -l ~/.ssh/known_host. This seems improbable to me.
If you haven't disabled StrictHostKeyChecking on the ssh client it may help narrow this down, as well. That option, normally the default, will cause ssh to fail to connect if it goes to the same guest-guestname-guestip and the fingerprint has changed. I see that isn't the trouble you are having, which is confusing if you are connecting to the same place over and over.
The time I see this is when I ssh into my guests and they have been assigned new IP addresses or when I ssh into them from a different account. (Each account has its own known_hosts file--they are not computer-wide).