What language was used to connect Europe and Byzantium?

Latin confirmed with a check in the Oxford Dictionary of Byzantium. Latin was clearly on the wane from the 7th century, but it seems not completely lost:

Lawyers preserved some knowledge of Latin, often superficial, from the 8th to 11th C., and Constantine IX’s novel establishing a law school in Constantinople prescribes the teaching of Latin. From the 11th C. onward, closer, if sometimes hostile, contact with the West led to increasing knowledge of Latin in leading Byz. circles; Romanos III spoke Latin and Psellos claimed some knowledge of it. Still, cultural arrogance usually marked Byz. attitudes to the West and its language.

Knowledge of Latin was even greater after the Fourth Crusade, and Maximus Planudes and the Cydones brothers even translated Latin works into Greek in the 14th century.

Nonetheless, Mehmed II’s diplomatic correspondence with the West was in fact in Modern Greek.