I have an entire star system under my empire's control, and the two other factions have the same. I have 8 envoys (one to a planet) for each of them, and can get all my pacts for each of them, but "Their relationship with you" is still in the negatives and there are no incoming envoys. My relationship with them is between 11 and 17.

It did before with just a Cease Fire, now even with a peace treaty, none at all. I even have 20.00 relationship with one of them!

I've noticed this to and I think the problem is with certain AI types (ie aggressive AI).  Aggressive AIs do not seem to bother making envoys no matter what the situation.  In fact, aggressive AIs are borked in general as they will tech up to maxiumum fleet supply (ie 75% upkeep!) without any concern as to whether their economy can support it.  At the end of one game, an aggressive AI I was at peace with had a credit income of...3.  Sure they had a huge fleet, but if they ever took major losses they simply could never recover.

Don't play with aggressive AIs unless you give them a massive cheating difficulty.

Oh. That makes sense. Though, the Reasearcher AI is doing the same thing... no envoys from them either.

I dunno man, they send Envoys in my game still.  When I was doing a 2v2 with all Vicious AIs they were actually offering pacts to me before I could establish my own.  Of course, the Vicious AI has multiple cheats; including those dealing with research times.  In 20 minutes a Vicious AI will have full logistic and tactical structures alongside 150 mines in each of their gravity wells.  Very vicious indeed. 

Researcher may be messed up too, I don't think I ever use it.  I have definitely seen envoys from fortifier and economist AIs, but Aggressor AI definitely does not.  In general fortifier and economist AIs seem to be the most difficult depending on the map layout, as they both concentrate on building up their infastructure before commiting to huge fleets.

Were they set to Aggressor AI, or random?  Difficulty just gives them resource and production hax.  The personality type is what sets their building and research priority.  Aggressor seems to almost totally ignore civilian research, regardless of how long the game goes on for.

Huh. Maybe I'll just play with Economist and Fortifier then. But are you sure that it had nothing to do with my playing with Small fleets? Cause in the game I played where I did get envoys I had it on Normal fleets.