iCloud Keychain breaks login for iMessage and FaceTime
I finally found a solution. 

The iCloud Keychain had several system keychain items. These items were not supposed to be in the iCloud Keychain and were overriding the "login" Keychain items whenever I would request login to Messages or FaceTime. 

I found the error by comparing my Keychain to a friend's laptop. I deleted everything from iCloud Keychain that was not in my friend's Keychain. (Well, anything that started with com.apple or ids.) (I left web page passwords.)

Once these deletions synced across devices, and I rebooted each machine, everything works perfectly.