What's the earliest example of a permanent embassy?

Question

In all the accounts I've read, when the great empires of the ancient Mediterranean needed to talk to each other, they sent an ambassador or a messenger. As in, someone from Country A brought a message to Country B, and then returned home. Of course, in modern times, most major nations have permanent embassies within the capitols (or other cities) of other nations, so that there's (for example) a British ambassador ready in Washington D.C. in case any British/American talks are required.

What is the first example of this? Was there a building or a home of a prominent Egyptian living in Rome during the time of the Republic, serving as the Pharaoh's representative? Did Charlemagne have a standing presence in Byzantium, or Philip II in England?

What is the first example of two sovereign nations having permanent, standing offices within each other's territories for the purpose of ongoing diplomatic contact?

Answer 1

Although I am late to the party since there is no accepted answer I will try to give mine. There are two cases I can think that might answer the question.

In ancient Greek city-states there were proxenoi. They were citizens of their respective city, but had friendly relations with another city-state and fulfilled some of the functions that are today in an embassy's jurisdiction. Additionally this position was hereditary in the family. From the Wikipedia page on proxenos:

A proxenos would use whatever influence he had in his own city to promote policies of friendship or alliance with the city he voluntarily represented. For example, Cimon was Sparta's proxenos at Athens and during his period of prominence in Athenian politics, previous to the outbreak of the First Peloponnesian War, he strongly advocated a policy of cooperation between the two states. Cimon was known to be so fond of Sparta that he named one of his sons Lacedaemonius.

The second example I found was papal agents stationed in Constantinople in the 8th century AD although it can be debated whether the Papal States constituted a sovereign state at the time. The relevant source can be found here:

Originally diplomats were sent only for specific negotiations, and would return immediately after their mission concluded. Diplomats were usually relatives of the ruling family or of very high rank in order to give them legitimacy when they sought to negotiate with the other state. One notable exception involved the relationship between the Pope and the Byzantine Emperor. Papal agents, called apocrisiarii, were permanently resident in Constantinople. After the 8th century, however, conflicts between the Pope and the Emperor (such as the Iconoclastic controversy) led to the breaking down of these close ties.

After those 2 examples, the next permanently established embassy is met in Renaissance Italy.

Modern diplomacy's origins are often traced to the states of Northern Italy in the early Renaissance, with the first embassies being established in the thirteenth century. Milan played a leading role, especially under Francesco Sforza who established permanent embassies to the other cities states of Northern Italy. It was in Italy that many of the traditions of modern diplomacy began, such as the presentation of an ambassador's credentials to the head of state.

Answer 2

The Amarna letters and other associated documents indicate the existence of permanent embassies in Egypt in the 14th century BC.

As a matter of practicality it has always been the practice to demand hostages among states in tension. For example, one king will send his son to be a hostage in the court of the other king. This son acts as a sort of an embassy. This practice can be considered to be primordial.