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.