Most coronations in the Catholic world have a line where the king pledges to be subservient to Papal authority in one way or another.
According to Wikipedia, at least, the coronation ceremony to become Holy Roman Emperor includes the following question from the Archbishop to the Emperor, to be answered "yes":
"Will you be duly subject and show reverent faith to the Father and Lord most holy in Christ, the Roman Pontiff and to the holy Roman church?"
Richard the First's coronation in 1189 had the king swear "that he would all the days of his life observe peace, honor, and reverence towards God, the Holy Church, and its ordinances."
The coronation of King Magnus of Norway in Bergen in 1164 had the king swear "to be obediens and fidelis to the Roman Church, acknowledged the papacy of Alexander, and confirmed the arrangements negotiated a few years before with the papal legate Nicholas Breakspeare (later Pope Adrian IV) about the liberties of the church in Norway and the payment of Peter's Pence."
Here's how I break it down: a king has language in his coronation saying that he will defer in at least some matters to the Pope. If the king fails to do so, the Pope is considered within his rights to exercise the Pope's temporal power (excommunication, crusade, etc.) to force the Pope's orders on the recalcitrant king.
Frederick II is actually a great example showing formal (if disobeyed) Papal authority over kings in purely temporal matters. Frederick II's first excommunication is for failing to go to war on the Pope's timetable; that is, the Holy Roman Emperor was obligated by the Pope to make war, as if the Emperor was a vassal of the Pope. Furthermore, as the 13th Century moves on, later Popes appoint Anti-Kings to Frederick II's successors in Germany, essentially claiming the right to name the "true" ruler of Germany.
Now, because Frederick II was a particularly deft politician and warrior, Frederick II could defy the Pope and keep his crown for his lifetime, although up to his death he was at war with some group or another allied with the Church. But that doesn't change that the Popes thought, and had many people with armies who believed, that the Popes had some temporal authority over every ruler in Christendom.