I disagree, many unpredictable things happen in EUIV diplomacy. Nations change rivalries, break alliances, there are events shaking things up, turns from-rival-to-ally, AI attitudes you cannot influence (you may do whatever you want but if AI nation has hostile/outraged/rival attitude you have very limited abilities to change its mind), dynastic policies (alliance breaking becouse of claim throne), sudden succession wars etc. AI isn't bad in EUIV in general, but still sometimes makes stupid things you couldn't predict, and sometimes those movements even work

I am currently playing Wallachia in eu4, very diplomatic heavy session (because of atrocious Wallachian geographic position - surrounded on all sides by three very powerful alliance blocs or empires, who hate each other) and diplo in this case is pretty satisfying.
I guess we just disagree about that. Yes, there are some random elements thrown into EUIV (e.g., chance of being discovered fabricating a claim, chance of ruler or heir dying, killing a royal marriage or disrupting a personal union), but much that you describe is attributable to the complexity of the diplomatic environment, with dozens of mathematically determinable interactions to keep track of and manage, not the consequences of "real" (i.e., human-like) diplomatic interactions.
I think of EUIV diplomacy as a very large, complex math problem. And like some math problems, the only solutions may be "imaginary roots" -- find yourself stuck amidst Austria, Hungary, Russia, several Hordes and the Ottoderps? Good luck managing that -- some game problems (and many real-life problems) are dilemmas (lacking a single, best solution), while others might have an optimal solution, if the "wet computer" between our ears had enough storage capacity and processing power to accurately assess the many interactions.
To be sure, sheer complexity is one "real life" challenge in managing international relationships (e.g., today, how can one reconcile the very different concerns and ambitions of the many parties with an interest in the South China Sea?), but randomness (or caprice) has a remarkably powerful impact on real world interactions. In a game, some randomness for flavor is good, but inject too much randomness and players will get frustrated (the AI is cheating....). Ask any game designer -- I'm not one, but they almost uniformly acknowledge that phenomenon among their player base.
So, can the sheer complexity of a problem be fun? Oh yeah, in the way any complex puzzle can be fun, but all too often players (maybe not you) find the fun in being able to explore the inner workings of a game's mechanics, ultimately to manipulate the game's systems to achieve their desired outcome (Three Mountains achievement anyone?), much more than they enjoy being blindsided by random negative events (seen any comets lately? did you enjoy that 15-year regency?), even though that sort of randomness is more "natural" or "true to life" than any game environment can provide. Accordingly, most popular games (and Paradox aspires to popularity as much as any game developer does) find a way to cater to that desire. EUIV certainly does so, although the sheer number of interactions you have to manage can yield a very complex, and therefore challenging, environment.
I've enjoyed my many hundreds of hours in EUIV, but I would not hold up its diplo system as a model for other games to emulate. Other games should implement their own, equally flawed, diplo systems. (Um, that doesn't sound quite right....)