This is the solution! Add the host key with the correct value from mailgunn to your config file.
host
Someone should update this in the documentation!