I lost many times when I was learning how to play, one AI factions, usually the Spanish or French, would become an Uber-power, and I couldn't field enough men to prevent them from crushing me. Also, Beating Egypt with the Almohads was impossible for me as a beginner, as they could easily rush me with camels and n00bian spearmen.

Once I better learned the intricacies of the game, I have only lost a few times, always from lack of heirs.