Your theory is basically right, in that your issue is caused by dyndns. More precisely, your issue is caused by having a dynamic IP address; dyndns makes things easier but not completely seamless.
When your router receives a new dynamic IP address (because it rebooted, or because your provider disconnected you for any reason¹) [step 1, step 4], you need to log in to the new IP. When your router connects, it sends a message to your dyndns provider notifying it of the address change. When you run
ssh johnny8888.dyndns.example.com, the ssh client looks up the IP address corresponding to
DNS information takes some time to propagate, because it is heavily cached. For typical dyndns use, the delay is a few minutes. So if you try to connect soon after an IP address change, you might still reach the old IP address [step 3], which is now attributed to a different machine. If this machine runs an ssh server, you get the remote host identification changed warning.
CheckHostIP No to your
~/.ssh/config, under the section for your router. Then ssh won't check the key associated with your IP address (which is useless since you have a dynamic address), only the key associated with your host name (which won't change).
Note that most of the time, you will not get the remote host identification change warning. You only get it if you try to log into somebody else's machine, or tried to in the past. (Your tries would be accidental, when you were unlucky to try connecting after an IP address change and before the DNS update had propagated.)
Many ISPs disconnect each client every day or every few days, because this facilitates their load balancing. You can reconnect instantly, but may get a different IP address.