I started getting the bogus error message "Apple ID is not registered with iCloud" sometime after Nov 22, 2017, when I sent my last successful invitation, and Dec 10, when I installed 2 new devices on my network. When they failed to show up on my iPhone after I installed them on my wife's, I revoked the old invitation and tried to send a new one.
A web search showed me the solution of removing all old invitations and issuing new ones. This works for some people, however if it fails it can leave you unable to send new invitations to those you revoked or anyone else.
I suspect that this bogus error message is a catch-all which really means "We can't send an invitation and we don't know why."
I have tried all the solutions given here, and spent two days at Apple telephonic help, 4 different people, removed and reinstalled all 20 of my devices, factory restored both my iPhones and my Apple TV 4 hub, replaced my router, and still have the same problem.
Dammit Apple, this is a disgrace. We pay you a premium for software that works. How about doing your job?