Well honestly I didn't say if it was feasible or not. But I do know its quite possible to get a a cease fire in under an hour without too much investment. Obviously if you need to put every effort into survival even this is not possible, but in this case its really not the AI's diplomatic handicap that is causing you problems, its the economic one which is the main reason its a "cruel" AI anyways.
Well I did some more test games.
The devs have definitely made it harder to get positive diplo with the AI and likely have boosted the ability for the AIs to build relationships between themselves.
I played a game as a Vasari vs 4 cruel AIs (2 TEC, 1 Vasari, 1 Advent). I got into a brouhaha with one of the TEC out of the gate (unavoidable as he wanted my blood) but the Advent neighbor was more ambivalent. I did every mission the Advent gave me (he hated my TEC nemesis as well) and sent several envoys (which ultimately still got blown up by the Advent player). The big thing I did is to not go after the Advent. I even conceded him one planet that he seemed to really want. My relations with him kept oscillating from ~1-2.2. Until ... I got strong enough that (a) I was not smallest fleet and ( started pounding the snot out of the TEC. Then my diplomacy boomed into the 5-5 range, albeit then the Advent were attacking more but half-heartedly.
I even went so far as to not have my ships or Orkulus attack the Advent early on when he came in with small forces into my northern checkpoint (used 'hold position'). Eventually he retreated and I guess his attention was focused elsewhere. This turned out to be a good choice since the Vasari player who was on the opposite side of the map from the Advent and behind the TEC I was hammering was in full alliance with the Advent after an hour (no idea how). Fortuitous since the Vasari player was at the time the strongest player on the board. Made my heart skip when the two jumped into my grav well but then the Vasari offered me cease fire (I was doing his missions also), which I took instantly. But if I hadn't already taken out 2 planets of the TEC who both parties also hated I would have been wiped out at that battle.
The biggest thing I can see is to bend over backwards to not piss off one of the neighboring AIs. But the new version no longer lets the human player manipulate things so easily with envoys and missions. Takes longer than before. Much longer. Meanwhile the AIs accrue diplomatic relationship between themselves MUCH faster. So be advised. It certainly introduces more randomness in the mix (staring conditions, etc.) Still on the balance locked teams are so boring and so damn easy.