"Screen Sharing could not verify the authenticity of xx.xx.xx.xx" <--- how to suppress?

My guess is certificates. How are you connecting to the computers? IP or computername.company.com (even without FQDN sometimes that works). I have AD computer certs on all our Macs and I don't get that message when I connect via IP or computername using the Screen Sharing app. I am prompted with a similar message when I SSH to any Macs from within Terminal, though.

Try looking in ~/Library/Containers/com.apple.ScreenSharing/Data/Library/Application Support/Screen Sharing Hosts for any .plist files. The signatures in these files must not match, that is why you're getting the error.

Is the computer at that IP address different than what was connected to before, or rebuilt, or otherwise modified? Or is the computer an imposter? That's what that message is trying to convey.