When and where did he exactly pay homage?
First time with Mieszko around 963, after the conquest of the Lebusians, when first agreed as a tributary duchy to the German crown. Reiterated several times (e.g. at Quedlinburg in 973), etc. Subsequently with Boleslav at Gniezno in 1000, homage subsequently at various interruptions during the German-Polish war, e.g. Merseburg in 1013 and then again at Bautzen in 1018. It ceases in 1025.
@Abdul Goatherd you're creating your own version of history. Already Otto I, Otto II and Otto III were crowned emperors. Many Polish dukes had problem with coronation, becasue emperor felt above kings and considered themselves privileged to conset to coronation.
Also there were many Bohemian kings, not dukes and not emperors, and all of them were vassals of the emperor.
Emperor is not "above king". That's a modern manner of speaking.
"Emperor" is a title in the Roman hierarchy, rooted in republican institutions, that has nothing to do with kings (Rome doesn't have kings). It is not in the Germanic hierarchy. Germanic monarchs are kings of a
folk, or people - Franks, Saxons, Lombards, Burgundians, etc. You are recognized as monarch by acclamation & elevation by the noble barons of the folk.
Lombards are not and have never been under Roman emperors. They have sovereign kings, acclaimed by Lombard barons, crowned with the iron crown of the Lombards in Pavia by the Archbishop of Milan. That's what gives a Lombard king authority over Lombard lords, who fiefs include most (but not all) of Italy, i.e. the Margraviates and Duchies of Milan, Friuli, Tuscany, Spoleto, etc. There is no higher authority.
Similarly, kings of Germany (i.e. East Franks and subjugated Bavarii, Thuringii, Saxons, etc.) are kings, acclaimed by German barons, crowned at Aachen by the Archbishop of Mainz. That's what gives the German king authority over nobles of Franconia, Swabia, Bavaria, Saxony, etc. There is no higher authority.
Similarly, kings of Burgundy are kings, acclaimed by Burgundian barons and crowned at Arles, by the Archbishop of Arles. There is no higher authority.
What is defined as the "HRE" (by Conrad the Salian, the guy who defined it) is the three kingdoms Conrad acquired, by gathering separate acclamations and coronations by the various groups of barons at Mainz, Pavia and Arles. And that is constitutionally what it remained down to 1806 (thus HRE had three chancellors, one for each kingdom - Arbp of Mainz for Germany, Cologne for Italy, Trier for Burgundy, etc.)
There is, in
addition a fourth title, the Roman imperial title, acquired by Conrad, which allowed him to exert sovereign authority over non-Lombard territories in Italy, i.e. the Romano-Byzantine lands of the Exarchate and the Papal States. You cannot be "king" over Romans, because Romans don't have kings. You need a title in the Roman hierarchy. Pepin was granted the title of Patricius, Charlemagne that of Imperator. So was Otto. Henry I was not. But Conrad was. And this is not particularly unique. Barbarian rulers over Romans in Britain and Romans in North Africa were also granted the "Imperator" title by local Roman authorities.
The title of "Roman Emperor" is a title bestowed by the Senate and People of Rome (SPQR), and crowned by the Pope at St. Peter's in Rome.
Emperor is not "above". It is separate. A Lombard lord will not recognize a Roman emperor as his sovereign. His sovereign is the King of the Lombards. Roman titles have zero authority over Lombards, and never have. And although Burgundian barons soon dispensed with the ceremony at Arles, and allowed the monarch to be crowned together with Germany at Aachen, Lombards did not. Until the 16th Century, you had to go all the way down to be crowned in Pavia, otherwise you are not.
Similarly, you have to go down to Rome to be crowned Roman emperor, otherwise you are not - you are merely "Emperor-elect"
So HRE collects four titles - King of Germany, King of Italy (Lombards), King of Burgundy, and Roman Emperor, three kingdoms plus extra bit. They are not above each other. They represent different areas, different folks. "HRE" is merely shorthand for all that.
These are the four titles acquired by Conrad, that remained definitive, and the basis of the constitutional structure of the HRE, which he was the first to define and remain unchanged since.
Later HR Emperors could acquire more titles and lands - and often did, e.g. King of Sicily, King of Hungary, etc. but as neither Sicily nor Hungary are part of the original Conradian titles, they were never part of the HRE, and never integrated into its structures. Similarly, Poland, which had once been a vassal duchy of the German king, slipped the noose before Conrad, and was never part of the HRE.
By contrast, the Duke of Bohemia remained a vassal of the German kingdom of Conrad, and thus became part of the HRE. The title of "king" was granted much later to Bohemian dukes as a courtesy title, but Bohemia always remained part of HRE.
Make sense?