Playing at 1 year per turn, I've gotten the warning in 1208 AD in two campaigns now, with the actual arrival of the first wave 4-5 years later. You could have missed them, you know. They can show up anyplace from Bulgar to Baghdad, so if they appear in the north and move west they'd skip you completely. There may also be a trigger tied to province ownership. It might not have them arrive if the human player owns their arrival province, I'm not sure about that one. If you own all 5 of those, they may be lost indefinitely.