yes and it is so annoying because AI rarely use envoys .

Some factions really hate one another which makes it extraordinarily difficult to make alliances with them, even with all the tech researched. A few combinations will be nearly impossible, even with a filled diplomacy tech tree. You must avoid war with the faction at all costs to make sure that you don't lose diplomacy for military action.

If you find that your relationship with them is high enough but theirs is not with yours, you can give them missions to give the mission relationship bonus to them as long as you have the mission tech researched. The "kill ships" mission and the "give resources" mission both work, but the resources takes less time for the AI to fulfill and gives the AI an extra bonus for resources given. Envoys don't work very well during the stage of trying to make an alliance as they die often and the death of the ship loses diplomacy points.

I don't believe they start sending envoys until you have a cease fire. You can actually get them to send them faster after the cease fire by using the "send envoy" mission, but that mission is only available to give after the cease fire. Once you get the cease fire, things should become much easier.

I hope this helped you, and good luck.

I never seem to have this problem. I completely ignore other races in the beginning and eventually someone comes along and offers a trade alliance and I accept because, hey, money! Then some other race will annoy me by trying to attack my frontier worlds or launching FU bombs at my planets and I'll rustle up a space posse and go kick their ass and suddenly I'm getting likes and friend requests out the wazoo....which I begrudgingly accept. Truthfully I hate everyone but I have to give people the appearance that I'm at least somewhat sociable. 

Then the diplo ships come, making my perfectly unicolored worlds unpure with the peppering of their filthy colors...and then I don't know why, but I feel guilted into sending my own envoys. And then it happens, we find ourselves laying in the same bed watching kung-fu movies and bickering over whose turn it is to take out the trash. 

This is actually pretty close to the truth. The best way to get a cease fire with someone is to blow up a lot of ships of someone they don't like. Research the relation modifier bonuses ASAP and try to get that trade agreement up for a slowly growing trade bonus. If you have at least 4.5 relations with them but they don't quite like you enough for a ceasefire, send them resources. Its a very fast way to get them high enough. Once you have that cease fire, then send your envoys.

That said, in Rebellion Diplomacy did get quite a bit harder. There is a new faction diplomatic modifier. For a few like the unofficial alliance of TEC Loyalists, Advent Rebels and Vasari Rebels, this can be slightly positive with each other. On the other end of the Spectrum, you have the TEC Rebels who absolutely hate almost everyone, up to -10 with the Advent and Vasari, which makes it almost impossible for them to ally with a non TEC faction. Also the points required for a cease fire got increased to 4.5 from 3.5 for some reason.

Any time I try a FFA with AIs, it always ends the same way:

-I kill a neighbour

-This pleases another AI

-We ally and double-team everyone else for an easy win

I realize it's probably difficult to implement proper diplomacy in a RTS and I doubt I could have done any better, but honestly it's better to just play with locked teams and not have to deal with easily exploited AI diplomacy.  Leave the diplomacy for turn-based games.

Trade should be chanced to Civic Diplomacy or something like that where Envoys, Missionaries, and Trade/Refinery ships are immune to fire. Diplomacy needs a slight rework.