Founding origin myths of Andorra claim that Charlemagne the Great (King of France and Holy Roman Emperor) granted the people of Andorra independence in 800 AD. I'm doubtful of this claim as no written historical evidence or references mention it. If Andorra was an ancient county of the Marca Hispania, I don't see it referenced in any historical documents. In fact, it possibly appears as a region in around 988 AD but it is unclear if there was any sovereignty of Andorra at not at least until around 1275 AD which it becomes a co-principality.
In 805, the date of alleged Andorran independence, the land around Andorra was ruled by Charlemagne.
Titles of European Hereditary rulers gives his title in February 806 as:
Karolus serenissimus augustus, a Deo coronatus magnus pacificus imperator, Romanum gubernans imperium, qui et per misericordiam Dei rex Francorum atque Langobardorum
That translates roughly as: "Most serene Emperor Charles, by God crowned Great Peaceful Emperor, ruling the Roman Empire, and by the Grace of God King of the Franks and the Lombards".
So Charlemagne claimed to be the Roman Emperor, and the most important part of the ideology about Roman Emperors is that they Were the rightful rulers of EVERYWHERE and EVERYONE.
So how could a tiny little realm like Andorra, right at the edge of a mighty state - or even surrounded by the territories of that state - whose aggressive and expansive ruler claimed to be the rightful ruler of EVERYWHERE and EVERYONE get acknowledged as an independent realm by that mighty state and its ruler? That seems like an impossible event.
Recognition of the independence of Andorra would seem to be impossible until such time as nether of its neighbors in Spain and France was the Emperor and thus compelled to claim lordship everywhere he could.
In 988, the Count of Urgel, a semi-independent ruler in Catalonia, gave Andorra to the Bishops of Urgel in Catalonia, who later became subjects and vassals of the Crown of Aragon. In 1095 the Bishop of Urgel and the Lord of Caboet in Catalonia signed a treaty making them co-rulers of Andorra.
In 1278 a conflict between the Bishop of Urgel (by then a vassal of the King of Aragon) and the Count of Foix (by then a vassal of the King of France), the heir to the Lord of Caboet, was settled and they continued to share the lordship over Andorra.
The heirship of the Lord of Caboet descended from the Count of Foix to the Kings of Navarre. Henry of Bourbon became King Henri III of Navarre in 1572 and King Henri IV of France in 1589. In 1607 he issued an edict making the head of the French state co-prince of Andorra along with the Bishop of Urgel, thus transferring the overlordship of Andorra from his Kingdom of Navarre to his Kingdom of France.
I suppose that after 1607 all the rulers of France considered Andorra to be another country that they were the (Co) sovereigns of and thus felt they didn't need to make Andorra part of France to have some authority over it.
To make an already long story short, I suspect that the exact answer to when Andorra became recognized as an independent state would be found in the diplomatic files of various European states, most importantly its neighbors France and Spain.
"Country" is derived from the Latin term for "land across the river". Thus, in history, nobody really talks of "countries" if they can avoid it. But we can talk about "states".
The claim that Andorra became independent in 805 could easily be a myth created to justify sovereignty. The Andorran government claims to have the charter of independence locked in a safe. We have no way of knowing what happened. If the earlier date is wrong, we know it became independent in 1278.