leap_cli should tell you that you need to redeploy to monitor node when hostkeys change
If you re-make a node, then the ssh host keys get re-done and the monitor node wont have the right keys to do check_mk checks against the nodes. You just have to "know" that you need to redeploy the monitor node with the updated keys. It would be good if leap_cli spit out a warning about this, so you would get a clue that this was needed!
(from redmine: created on 2015-06-09)