There are several issues raised in the question:
The legal issue is quite clear and was addressed in other answers.
"... how these leaders justified NATO's expansion. Surely someone would have asked them why they are breaking their promises. How did they respond? I'm asking about these named leaders who made the promises only."
This question also has a very simple answer: Except for Helmut Kohl, none of them was a leader of their respective country when the NATO expansion took place (and Kohl was out during the 2nd round of expansion). As for future leaders, oral promises made by their predecessors are not binding in any sense (legal, political or moral).
- As for debates within NATO on wisdom of enlargement(s), these are amply covered for instance in the book
"Who Lost Russia?: How the World Entered a New Cold War" by Peter Conradi.
Here are few relevant fragments from the book:
“IN THE YEARS SINCE 1999 THERE has been much discussion about NATO enlargement and whether the West broke a promise by pressing ahead with it. Each stage in the deterioration of relations between East and West has been marked by new claims of pledges made and broken. Attention has focused in particular on a conversation between Gorbachev and James Baker, Bush’s secretary of state, in February 1990, during which Baker pledged that if Soviet forces were withdrawn from Eastern Europe, NATO would not move in to replace them. The ‘military presence or jurisdiction of NATO would not be expanded even one inch in an easterly direction’, Baker had told Gorbachev, according to transcripts of the conversation. Helmut Kohl, the West German leader, gave similar assurances. This idea of NATO’s ‘broken promise’ became a cornerstone of Russia’s post-Soviet identity. NATO itself has conceded that some statements by Western leaders, especially those by Baker and by Hans-Dietrich Genscher, his German counterpart, ‘can indeed be interpreted as a general rejection of any NATO enlargement beyond East Germany’. John Major, the British prime minister, was even more explicit, telling Dmitri Yazov, the Soviet defence minister, in March 1991, that he
did not himself foresee circumstances now or in the future where East European countries would become members of NATO’, according to the then British ambassador, Rodric Braithwaite, who was present at the meeting. Yet, despite the opening of countless records and releases of archival material, it is clear that the assurance “remained just that. No legally binding written guarantee has ever emerged. In any case, such statements were made in the context of the negotiations on German reunification, and the Soviet side never specified their concerns. Nor was the issue raised during the crucial ‘2+4’ negotiations that finally led Gorbachev to accept a unified Germany in NATO in July 1990. At that time the Warsaw Pact still existed, and Poland, Hungary and the then Czechoslovakia, among others, were still members. As Gorbachev’s foreign minister, Eduard Shevardnadze, put it, the idea of the Soviet Union and the Warsaw Pact dissolving and NATO taking in former Warsaw Pact members was beyond the imagination of the negotiators at the time.
According to this argument, the disbanding of the Warsaw Pact in February 1991 and the break-up of the Soviet Union at the end of the year created a completely new situation: freed from Soviet control, the countries of Central and Eastern Europe were finally able to choose their destinies again. Given that they were all set on integration with the West, refusal by NATO to accept them would have meant a de facto continuation of Europe’s Cold War division and a denial of the provision, enshrined in the 1975 Helsinki charter, for a country’s right to choose its own alliance.
Within Russia, criticism has inevitably focused on Gorbachev himself and his failure to secure a binding guarantee that ruled out any eastward expansion of the Alliance. So many other minor issues that came up during negotiations
were addressed in formal documents. Why did he not demand the same for something as important as enlargement? The charge clearly rankles with the former Soviet leader. In the years since, Gorbachev has condemned enlargement as a blunder and contrary to the spirit of the undertakings that he was given. Europe’s long-term security would have been better served by the creation of new institutions that would have united the Continent rather than preserved its division, he claims. Yet he has also dismissed as absurd any suggestion that he was outwitted by the West.
‘German reunification was completed at a time when the Warsaw Pact was still in existence, and to demand that its members should not join NATO would have been laughable,’ Gorbachev wrote in his book The New Russia, published in 2016. ‘No organisation can give a legally binding undertaking not to expand in the future. That was a purely political question, and all that could be done politically in the condition of time, was done.’
Regarding the first stage of NATO enlargement. A summary is that the issue was not taken lightly, but the concerns were not about any "broken promises" (the principals of the conversation were no Spring chickens and understood very well what these promises were worth), but political ramifications.
Russia remained alarmed at the prospect of the Alliance’s advance towards its border. So, too, was Jacques Chirac, the French president: determined to create a European position that differed from that of the Americans, he argued that NATO should not press ahead with enlargement without Moscow’s approval. During a meeting with Talbott in January 1997, Chirac accused America of mishandling the issue and failing to appreciate Russian sensitivities. He suggested that he and Helmut Kohl should negotiate with Yeltsin. But the German leader rebuffed him; he was keen to have Poland in NATO since it would mean his own country would no longer lie on the Alliance’s eastern border. Clinton was also becoming jittery. At a cabinet meeting on 17 January 1997, he asked what was in it for Yeltsin. He was
told Russia would be offered membership of a joint consultative body with NATO and some modification to the terms of the Conventional Forces in Europe (CFE) Treaty. Clinton was sceptical. ‘What the Russians get out of this great deal we’re offering them is a chance to sit in the same room with NATO and join us whenever we all agree to something, but they don’t have any ability to stop us from doing something that they don’t agree with,’ he said. ‘They can register their disapproval by walking out of the room. And for their second big benefit, they get our promise that we’re not going to put our military stuff into their former allies who are now going to be our allies, unless we happen to wake up one morning and decide to change our mind.’
Commentators weighed into the battle. Old Cold Warriors such as Kissinger and Brzezinski came out in support of enlargement. ‘Now that Soviet power has receded from the centre of the Continent, the North Atlantic Treaty Organization needs to adapt itself to the consequences of its success,’ said Kissinger. Others in America were warier, warning of the danger of provoking Russia and questioning why the proposal had not been the subject of congressional hearings. Just because former Soviet bloc countries wanted to join NATO didn’t mean it was in the Alliance’s interests to admit them, they argued, nor would it necessarily enhance America’s own security. The West was about to ‘make perhaps the biggest mistake of the post-Cold War period: rushing to expand NATO without satisfactorily resolving our relationship with “Russia first’, Susan Eisenhower, chairwoman of the Center for Political and Strategic Studies, wrote in the Washington Post in March 1997, four months before the summit at which invitations were to be issued to the newcomers. On the other side of the Atlantic The Times also joined the critics, attributing Clinton’s enthusiasm for enlargement to his desire to please the Polish constituency in Michigan. ‘European and American leaders are but months away from implementing a plan that risks undermining the credibility of NATO, weakening the hand of reformers in Russia, and reducing – not enhancing – the real security of the countries in Central and Eastern Europe,’ it thundered.
Opponents of enlargement also found a powerful champion in George Kennan, the doyen of US foreign policy, whose Long Telegram, written in February 1946, set out the principle of the Cold War strategy of ‘containment’ of the Soviet Union. By then in his nineties, Kennan did not mince his words. ‘Expanding NATO would be the most fateful error of American policy in the entire post-Cold War era,’ he wrote in an opinion piece for the New York Times, entitled ‘A Fateful Error’. “Such a decision may be expected to inflame the nationalistic, anti-Western and militaristic tendencies in Russian opinion; to have an adverse effect on the development of Russian democracy; to restore the atmosphere of the cold war to East–West relations, and to impel Russian foreign policy in directions decidedly not to our liking.”
Kennan’s article, which appeared on 5 February, on the eve of a visit to Washington by Viktor Chernomyrdin, had considerable impact. Talbott had been tipped off about it by Kennan before it appeared and a clipping of it was lying on Clinton’s desk in the Oval Office when Talbott joined a meeting there. ‘Why isn’t Kennan right?’ Clinton demanded. ‘Isn’t he a kind of guru of yours going back to when we were at Oxford?’ Talbott was unfazed, pointing out that the veteran diplomat, despite his reputation as a Cold War warrior, had been opposed to the creation of NATO in the first place. So why take his comments seriously? Clinton, he felt, was convinced. ‘Just checking, Strobe. Just checking,’ the president smiled.”
“The stage was set for a difficult summit. Clinton’s strategy was to make it clear that enlargement was going to happen but to look for ways to sweeten the pill and make it easier for Yeltsin to sell the results at home; he aimed to do so by setting a target date for Russian accession to the World Trade Organization and turning June’s Denver G7 Summit into something more like a G8. ‘We’ve got to use this thing to get . . . [Yeltsin] comfortable with what he’s got to do on NATO,’ Clinton told Talbott.
The summit ended with the inevitable: a grudging acceptance by Yeltsin of enlargement, though not before the Russian leader had made one last attempt to persuade Clinton to agree that NATO would not ‘embrace’ any of the former Soviet republics. This need not be something formal, Yeltsin suggested: a secret ‘gentleman’s agreement’ would suffice. Clinton insisted, however, that there could be no question of a veto on any country’s eligibility for NATO, especially not in the form of a secret deal, details of which were bound to leak out to the press. He did not want to stand accused of agreeing to a modern-day version of the Molotov-Ribbentrop Pact under which Hitler and Stalin had divided up Central Europe. Once they were alone, Yeltsin revealed to Clinton that he was concerned about a backlash at home. ‘Boris, do you really think I would allow NATO to attack Russia from bases in Poland?’ Clinton asked. ‘No,’ Yeltsin replied, ‘I don’t, but a lot of older people who live in the western part of Russia and listen to Zyuganov do.’ Clinton realised that Yeltsin was deadly serious. As he later explained to Tony Blair, who became British prime minister that May, it was important to understand the Russian mentality. ‘They are still affected by Napoleon, Hitler and the way the Cold War came to an end, and about the way the Soviet Empire collapsed,’ he said.
... Clinton had squared the Russians, but now he faced the equally difficult challenge of getting the NATO allies on board. While enlargement was widely backed within the Alliance, there was no agreement on how many countries should be invited to join in the first wave. Washington wanted to limit it to Poland, the Czech Republic and Hungary, not just because they were the most prepared, but also because the more members there were, the more complicated the problem of assimilating them would be. But a majority of NATO members wanted a larger number: Chirac, having swung round to accept enlargement, lobbied hard for the inclusion of Romania. Others wanted Slovenia or Slovakia. An insight into Clinton’s thinking came from a conversation he had over lunch with Blair in Downing Street that May. During it, he dismissed as a ‘silly argument’ suggestions by critics of enlargement in Congress that it could provoke a nationalist backlash in Russia. When Sandy Berger, Clinton’s newly appointed national security adviser, noted that polling data showed NATO was not a ‘grass roots’ issue “for Russians, Blair chipped in, saying: ‘What a surprise – they are just being normal and caring more about the economy.’ Clinton was adamant, however, that the first wave of enlargement should be limited to three countries. ‘Our first concern is that the first shall not be the last – we have said that all along,’ he told Blair. ‘If there are five, no one will believe in a second round and we will be under pressure to reassure them [the countries not admitted] publicly . . . The open door must be credible.’ A larger group would also ‘turn up the heat on the Baltic issue’ – the even more contentious matter of NATO membership for Estonia, Latvia and Lithuania – ‘and we are not prepared to handle that yet. This is a problem that needs time to sort itself out; we need to give it a few years.’ The issue came to a head at a meeting of NATO foreign ministers in Sintra, Portugal on 30 May, the day after Clinton’s meeting with Blair. Although backed by just Britain and Iceland, Washington ultimately prevailed, not only because of its undue weight within NATO but also because of the principle of consensus on which the Alliance worked. Invitations were extended only to Poland, the Czech Republic and Hungary, but the communiqué established the principle of the ‘open door’, a process for the consideration of future applicants.
Regarding the second stage of the NATO expansion:
...NATO enlargement was even more divisive. Since his summit with Clinton in June 2000, Putin had continued to send out mixed signals about the Alliance. In July 2001, during his first press conference as president, he had urged that NATO be disbanded, dismissing it as a relic of the Cold War. ...
In the aftermath of 9/11 attacks:
... in a reflection of the changed international situation since 9/11, Putin again raised the subject of Russian membership of NATO during a private meeting with Robertson at Alliance headquarters in Brussels. ‘Mr Secretary General. When are you going to invite us to join NATO?’ he asked his host. Robertson replied that no country was ever ‘invited’ to join the Alliance. They had to apply.
Putin was not impressed. ‘Russia is not going to stand in a queue with other countries that don’t matter,’ he said. Robertson suggested they ‘stop the diplomatic sword dance about membership and build the relationship between us’. ‘And that’s what we did,’ he says. It was the last time Putin spoke about joining NATO....
Much more can be said, but, I think, this answer is already too long.