What did I missed from Dom I.? -> DIPLOMACY!

[Endoperez]

You can also do diplomacy by sending the maps/whatever you have and some comments, to the one you believe is your ally, outside of the game. And you can lie as much as you want, and even edit the maps' information if you know how to use paint... The only greater problem is that you have to know your co-players e-mail address. E-mail because normal mail might get too expensive, and is quite a bit slower.

About SP diplomacy, it might be good addition but it might be too much.
The AI would have to check how strong your dominion is, what scales you have, might your dominion with quite a few negative scales be pushed towards its lands by stealhy preachers, check your every battle or keep book of its provinces to be sure you don't have a theme that hurts it, and everything else that human player might come up with...
Just try to list everything AI should take into account, and you might have a glimpse about how hard coding a decent AI for DomII is. Not that I have even that, of course.