When was the first confirmed circumnavigation of Africa?

I'd like to mention another possible candidate for this honor, one João Bermudes, who could have accomplished this feat depending on how one defines "circumnavigate Africa", but he clearly made his way around this continent at least once, if not twice.

Bermudes is one of these sketchy characters whom one encounters in history: a person of no great abilities, nevertheless manages to find a golden opportunity which he uses to hustles his way into power & prestige, only to be revealed to be a fraud & cast out. He was a minor member of the first Portuguese embassy to Ethiopia in 1520, sailing with the ambassador from Portugal to Massawa on the Red Sea coast, by way of India. He is remembered in that group for two things: suffering a serious injury while wrestling one of the native Ethiopians (IIRC, he broke his leg); & as one of two people left behind to learn the language as a benefit for the Portuguese king when the ambassador left to return home. (Or that was a convenient excuse to leave Bermudes behind because he had been such an annoying jerk.)

When the ambassador left, things looked very good for the Ethiopian emperor, Dawit III. However, a few years later a Muslim Imam Ahmad Gragn, led a Jihad against the Christian polity, won several battles & conquered most of Ethiopia. Things were desperate by 1531 & Dawit assigned Bermudes the task to travelling to Europe to ask for help. Since Bermudes was a lone individual with no real standing amongst the Portuguese government, he could not return to India & seek passage back to Europe that way, so he was forced to somehow make his way to the shores of the Mediterranean & seek passage from there. (There is evidence that he was in Rome before he reached Portugal.) So it can be argued at this point Bermudes circumnavigated Africa, although not in one trip, & perhaps not entirely by ship.

Bermudes Ethiopian adventure did not end there. When he appeared in Europe, he claimed to be the Patriarch of the Ethiopian church, having been duly appointed & consecrated by emperor Dawit III. Failing to make much of an impression on the current Pope, beyond receiving some money for his immediate needs & further travel expenses, Bermudes proceeded to Lisbon where he was more warmly received. The idea of a crusade on behalf of the Ethiopians sounded good to some members of the Portuguese court, so he was included in the party of the new Viceroy of Portuguese India, Estêvão da Gama, & arrived in India by 1540. That same year da Gama prepared a naval expedition to attack the Ottoman fleet stationed at Suez, which included Bermudes.

The Portuguese attack on Suez came to naught: da Gama found he had too few ships to successfully attack the Ottoman fleet. Moreover, upon returning to Massawa where he had left a group to secure his rear, he discovered that Bermudes had incited a near-mutiny over the cause of rescuing Christian Ethiopia from the Muslims. Da Gama, seeing this was the easiest course, gave in to the demands of his men. He allowed 400 volunteers under the command of his brother Cristóvão da Gama to land & come to the aid of the local Christians. This Cristóvão succeeded in doing, defeating & killing Imam Ahmad Gragn but at the cost of his own life. And João Bermudes became a central figure in the court of Dawit's son, the Emperor Gelawdewos, claiming he had been appointed & ordained Patriarch of Ethiopia by the Pope.

At this point we have an exchange of letters between governments. One from Gelawdewos to King John of Portugal, asking, in essence, "Who is this João Bermudes fellow? And why does he behave so irresponsibly?" To which John of Portugal replied, in essence, "I dunno. He says your father made him Patriarch. The Pope claims he didn't do it." Shortly afterwards Bermudes found himself exiled to the edge of Ethiopia. He managed to find his way back to the court, only to be exiled a few more times until he found his way aboard a Portuguese ship & made his way back to Portugal. (Technically, he was supposed to receive permission from the Emperor to leave his realm, but by that point the Emperor was content to look the other way & be done of him.)

One could argue that his journey home took him thru Ottoman territories once again, but it is more likely he sailed on a Portuguese ship from India around the Horn. So a second circumnavigation would be unlikely.

Bermudes would likely have been forgotten to history had it not been that he read an account of Cristóvão da Gama's heroic expedition into Ethiopia, decided it made him look bad & wrote his own account of his second sojourn in that land. The translator of Bermudes' memoir, R.S. Whiteway, considers the entire work so much fantasy but having read the translation I find some of the details -- which do not touch on da Gama's actually military expedition -- plausible.

The Egyptian/Phoenician circumnavigation of Africa you refer to is recorded by Herodotus:

For Libya shows clearly that it is encompassed by sea, save only where it borders on Asia; and this was proved first (as far as we know) by Necos king of Egypt. He, when he had made an end of digging the canal which leads from the Nile to the Arabian Gulf, sent Phoenicians in ships, charging them to sail on their return voyage past the Pillars of Heracles till they should come into the northern sea and so to Egypt. So the Phoenicians set out from the Red Sea and sailed the southern sea; whenever autumn came they would put in and sow the land, to whatever part of Libya they might come, and there await the harvest; then, having gathered in the crop, they sailed on, so that after two years had passed, it was in the third that they rounded the Pillars of Heracles and came to Egypt. There they said (what some may believe, though I do not) that in sailing round Libya they had the sun on their right hand.¹²

Book 4, chapter 42

And there's a footnote by the editor of the 1921 Loeb Classical Edition, from which this translation came:

¹²The detail which Herodotus does not believe incidentally confirms the story; as the ship sailed west round the cough, the sun of the southern hemisphere would be on its right. Most authorities now accept the story of the circumnavigation.

Historians today don't always take Herodotus at face value. According to livius.org, 2nd Century CE geographer Cladius Ptolemy didn't believe it was possible. The Nile Canal was closed in 767 by Caliph Al-Mansur to put down a rebellion and it silted up. So no other circumnavigation of Africa and only Africa was possible until the Suez Canal opened in 1859.

You can believe Herodotus or not; it's the only chance before 1859.

Except there's a technicality.

In 1519, Ferdinand Magellan set out with 5 ships and 250-270 men. After three years and several mutinies and battles, and much hardship and starvation, a single ship, the Victoria, managed to return to Spain with captain Juan Sebastian Elcano, Italian historian Pigafetta, and 16 others. As a consequence of the first known circumnavigation of the Earth, these guys managed to circumnavigate not only Africa, but also Europe, Asia, and the Americas. That's what happens when you sail a closed loop on the Earth, you're likely to circumnavigate something.

Note: There appear to be some people interpreting a mere passage around the Cape of Good Hope as a "circumnavigation" of Africa. That is clearly not the intent of the OP, and a mischaracterizaton of what the Victoria did. By Sailing all the way around the Earth, Elcano, Pigafetta, and their companions completed a closed loop with Africa inside. That's a circumnavigation.