I'm getting the dreaded "Offending ECDSA key in /var/lib/sss/pubconf/known_hosts" message when I ssh to a particular host:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ECDSA key sent by the remote host is
5a:b5:f5:9b:93:d9:7b:58:06:a4:50:83:aa:bf:a8:96.
Please contact your system administrator.
Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /var/lib/sss/pubconf/known_hosts:4
ECDSA host key for ulrhnsat01 has changed and you have requested strict checking.
Host key verification failed.

This host was just rebuilt from scratch. I have deleted its host entry from IPA. I have stopped sssd, deleted ALL the entries from /var/lib/sss/pubconf/known_hosts, and restarted sssd, but the problem persists and /var/lib/sss/pubconf/known_hosts gets rewritten to its original value.

How do I fix the problem?