Yes, this does happen. It may have to do with balance of generals with provinces. Its happened to me about once per game. A candidate for adoption will be offered, and at the end of the turn cycle, a final notice will come that the "adoption failed".
There are six messages that can appear, as in \Data\text\event_strings.txt:
{adoption_failed_body_roman}Your messenger arrived just too late with your generous offer of adoption. Unfortunately, the man is now deceased.
{adoption_failed_body_barbarian}Your messenger was delayed, and this man is now dead - and so cannot be adopted.
{adoption_failed_body_carthaginian}Your messenger was lax and tardy, and this man has unprofitably departed to join his ancestors...
{adoption_failed_body_greek}Your messenger lacked a certain fleetness of foot, and the man who should have been adopted has died and gone to Hades instead.
{adoption_failed_body_egyptian}The messenger was a tardy snail rather than a fleet-footed and loyal servant of the Pharaoh. This man has died in the interim, and cannot be adopted!
{adoption_failed_body_eastern}Your messenger should be fed to the dogs for not moving with more speed. This man has died before the adoption invitation could reach him!
When the adoption fails, you will get the "Adoption Not Completed" message.
I don't know the odds; I think it is somewhere between one in 5 and one in 10. It may be coupled, in part, to getting a Man-of-the-Hour adoption between turns, but I've not tested for it.