A couple of guesses, on top of all the other info, jump to mind...
Could be an incorrect message (it happens) in that Apple might be using some sort of verification process to see if domain is legit. I've seen that when I don't want to give a real email address to a site, and it complains that the address is not valid. Might take some time for the domain to become "valid" across verification sites/services.
Or, domains are not forever if one does not renew it. So, maybe, someone had the domain in the past and used it for their Apple ID. Guess would be really long shot, as user id on domain would need to be same as one being fed to Apple.