Why did the Caliphate fear Justinian II?

Derrick asks how Justinian II was able to exact tribute from the Caliphate.  Though certainly colorful, the great, great grandson of Heraclius was a disastrous emperor.  Only 17 when he took the throne, his heavy taxes soon made him unpopular with the rank and file, and his disdain for the Senate alienated the nobility.  After a decade he was so despised that a mob in the Hippodrome deposed him, cut off his nose and split his tongue.  Somehow he managed to claw his way back from exile (with replacement gold nose in tow), sneak into Constantinople through an unguarded aqueduct and regain his crown.  The next six years were spent killing anyone who looked at him sideways until the fed up population overthrew him again- this time cutting off his head to be sure there wasn’t a third reign.

So how did such a dreadful leader manage to exact tribute from the Caliphate?  That was largely through the hard work of his father Constantine IV and grandfather Constans II.  They had energetically opposed the surging armies of Islam and largely stabilized the eastern provinces of the empire.  Constantine IV even forced Caliph Abd al-Malik into signing a peace treaty and started to think about going on the offensive, but he died at age 35 before any serious preparations had been made.  Fortunately for the empire the new emperor Justinian II was an unknown quantity and Al-Malik, concerned about revolts within the Caliphate and fearing new Byzantine attacks decided not to risk it.  He renewed the treaty, sweetening the pot by agreeing to increase the yearly tribute and share the income from Armenia, Iberia, and Cyprus.

It must have seemed at first as if the Arabs got the better end of the deal.  Justinian spent the next five years demonstrating that he had fully inherited his family’s military ability. A campaign against the Slavs restored the Balkans to imperial control and a second one drove the Bulgars out of northern Greece.  Turning east, he swept into Armenia and Iberia and the show of strength convinced the Caliph to increase the annual tribute.  By now, however, Justinian II had convinced himself he was his famous namesake and was no longer satisfied with tribute.  He drafted the defeated Slavs into his army and invaded the Caliphate.  The conscripted soldiers took the first opportunity to desert and the outnumbered Byzantines were easily routed.  The Arabs seized Armenia and Justinian II returned to Constantinople to find the populace fed up with his overbearing ways and the taxes needed to fight his never-ending wars.

By the time he regained his throne the pain and suffering had unhinged his mind.  The international situation had drastically changed during his ten years in exile, but all he cared about was revenge.   As the frontiers collapsed around him he descended into a bloody reign of terror.  The empire paid the price of his negligence.  Only six years after his death an Arab army was at the gates of Constantinople poised to extinguish the empire.

With this record it’s hardly surprising that Justinian II doesn’t fare well with historians. The golden nose and brutal reprisals tend to overshadow any more mundane accomplishments, and he’s almost never given credit for his real abilities.  The last descendant of Heraclius may have had lousy judgment, but he was no slouch on the battlefield.