Jenkins and Maven SCP Error: reject HostKey

We lost one of our internal build machines recently (that was a sad day), and so we've been rebuilding our Jenkins environment from the ground up. We use scp access for our distributionManagement control in Maven. Because of this, Jenkins broke on our first build with a whole lot of output saying "The host was not known and was not accepted by the configuration", which narrowed down to this exception:

Caused by: com.jcraft.jsch.JSchException: reject HostKey