I think this is related to the type of AI (offensive, researcher, etc.) the AI is, it seems some of the templates are bugged and won't send envoys, while at least one type does.
I had 3 friendly AIs in one game and only 1 sent envoys when I gave the mission. Though as they were set to random, I can't reconstruct this assumption for sure.