If memory serves, the origingal Iberian problem was that the Iberian Muslims had an ICBM-like tech edge over the Iberian Christians, resulting in the complete annihilation of all Christian states in Iberia even before the first Crusade was called. It was so bad that even a human playing Castile on very difficult got wiped out 90% of the time, and only conquest of Muslim provinces, and thus Muslim wealth and tech, made the situation winnable for a human. What made it worse was the lack of Crusade targets under 1.04, resulting in lack of Crusade incentive to liberate the Christians in Iberia for the AI. (Humans had every reason to liberate Iberia for all of the free provinces once they narrowed the tech gap.)
The situation in Iberia has been improved by several orders of magnitude. Now, it is a crap shoot who will dominate in Iberia. Most of the time, it's Castile. Sometimes, Sevilla wipes everyone out and holds out against Crusades. Other times, Germany and France partition it when the Muslims win. Aragon now actually survives some of the time and becomes a real kingdom. It is even tenable to play Navarra.
All of the things you mentioned as problems are not Iberian Problems. They are just CK quirks. The Baltic pagans, even with their helpful troop events and the pagan revolt events, are just as easy to wipe out as the Iberian Muslims. If you don't believe me, take Denmark for a spin and conquer the Baltic pagans before the Crusades fire. With all of the problems the Fatamids have, you can easily carve out a Kingdom of Jerusalem by yourself once you have about 15,000 troops that you can afford to ship to Acre. And the enterprising Russian Prince has plenty of targets which allow him to grab the provinces needed to become King of Rus or Bolgar (now that Rus has fewer provinces), resulting in sudden swearings of allegiance. The fact that the AI unifies Rus itself about 33% of the time in my 1066 games indicates that Iberia is by no means the only place where religious war can result in insane gains in real estate.
The Iberia Problem is gone. As for the rest of these issues, that is a different debate.