It had to happen sometime. Notwithstanding that sensational '97 election result, and the intimidating scale of Mr Blair's Commons' majority, the one infallible rule of politics remains, that what goes up must eventually come down.
And yet. And yet. . .long after it seemed either probable or desirable, "Teflon" Tony continued to show himself curiously immune to the normal rules of politics.
There were early warning signs - although those hoping for blood when it emerged that Jack Straw's teenage son had been arrested for buying £10 sterling worth of cannabis from a tabloid reporter were confounded by the spectacle of the Home Secretary, family and dignity intact, emerging as one of the cabinet's most impressive performers and true heavyweights.
Other already-established heavyweights didn't fare so well. Robin Cook, already hurt by revelations about his private life, came under pressure to resign after allegations that the Foreign Office had colluded with mercenaries to help restore the president of Sierra Leone.
Little more would be heard of New Labour's "ethical foreign policy" - a phrase, indeed, for which the Foreign Secretary would later disclaim responsibility. But Mr Cook survived (and here's the rub) at the prime minister's insistence.
Chancellor Gordon Brown emerged damaged, too, after an effectively-authorised biography told the wider world what the Westminster chattering classes already knew - that Gordon remained bitter and resentful that it was Tony, and not him, who had landed the top job after John Smith's death. A vicious war of words ensued between the rival camps of "spin doctors" inside Numbers 10 and 11 Downing Street. But things threatened to get seriously out of hand when one unnamed source described the Chancellor as "psychologically flawed", and Mr Blair himself took the lead in effecting a public reconciliation. With all their customary disdain for `media froth', the spin doctors let it be known that Chancellor and Prime Minister remained the best of friends. Nobody quite believed it - and the latent tensions between the two most powerful members of the government would be dramatically revived when the bombshell finally hit Westminster.
Yet if messrs Cook and Brown were diminished by such episodes, they served only to enhance the sense of Tony's greatness and of the government's reliance on him. Questions about Postmaster General Geoffrey Robinson's off-shore trusts and business dealings would dog the government until his eventual departure.
But the writing was already on-the-wall when the family Blair decided they would not, this year, holiday at Mr Robinson's Tuscan villa.
The Blair government was notching-up an impressive number of solid achievements with breathtaking speed. Following the successful referendums, parliament was enacting the legislation for the Scottish Parliament and the Welsh Assembly. An extra £40 billion was found for health and education spending, while David Blunkett continued his efforts to extend the educational choices the middle-classes had long made their own. The New Deal was tackling the pattern of long-term unemployment among the young, while ministers continued to address the problems of social exclusion and alienation.
With the Tories nowhere, Mr Blair continued to fly high in the public's esteem. When he travelled to Labour's Blackpool conference in October, it was to record approval ratings for a prime minister 16 months in power. William Hague, by contrast, travelled to Bournemouth to news that 20 per cent of those polled failed to recognise him. On arrival, he found Ken Clarke and Michael Heseltine dismissing his "principled" opposition to British membership of the euro for at least 10 years - and the Sun pronouncing him the leader of a "Dead Parrot Party".
The frustration for the young Tory leader was that his impressive, and sometimes wounding, Commons performances against Mr Blair still found no resonance in the country at large. Even there he faltered, in November, when an assault on the government's plan to abolish the hereditary peerage, and the ambiguity of its designs for a reformed second chamber, spectacularly backfired upon discovery that Mr Blair had already stitched-up a deal with the wily Lord Cranborne.
The resultant fallout cost Mr Hague his leader and six front-bench spokesmen in the Lords; effectively lost him the hereditaries as an opposition force; and, in the process, revived questions about his own survival prospects.
Mr Blair could scarcely believe his luck, even though he knew it couldn't last. Amid persistent predictions of possible recession, and with his own position on the single currency unresolved, the striking feature of his conference speech indeed had been his warning of a difficult and challenging year ahead.
Within eight weeks he had lost three senior ministers. Ron Davies' departure as Welsh Secretary after "a lapse of judgment" on Clapham Common triggered a gay witchhunt, which led to the enforced "outing" of Agriculture Minister Nick Brown. The benign result of this (although not for Mr Brown, who had wished to keep his private life precisely that) was something of a backlash against the tabloids, the realisation that attitudes had moved on and that, as far as the public is concerned, being gay and in the cabinet is OK.
However, over several days of rueful reflection at Chequers, Mr Blair will have discerned no benign consequence to the sensational events which forced Peter Mandelson from the cabinet - and Mr Robinson, finally, in his wake - just two days before Christmas.
As the shock waves reverberated throughout Whitehall and beyond, the fault-lines of cabinet factionalism were laid bare. Accusing fingers pointed toward Treasury sources amid talk of a "plot" to bring about Mr Mandelson's downfall. Memories of "Drapergate" and the Bernie Ecclestone/Formula One affair were revived as one Tory newspaper, pushing it somewhat, suggested Labour had achieved a level of sleaze after 18 months which had done for the Tories after 18 years.
Peter Mandelson was in many ways the keeper of the modernising flame. The accredited architect of New Labour had come to be seen as the enforcer of that process of change essential to New Labour's contract with the people of Middle Britain - the process which had persuaded them they could abandon the Tories without fear or threat. And for that reason (witness the unconcealed joy on the Labour left, and among "Old" Labour ministers) his loss was a deep, personal blow for Mr Blair.
The charges attendant to his departure - vanity and greed among them - have been seized upon by critics of Blair himself to suggest the time is right to reassess this government's emphasis on style over substance and, crucially, to reconsider its attitude to the world of business.
Aside altogether from questions about propriety and disclosure on mortgage application forms, the scale of Mr Mandelson's borrowing to sustain a lifestyle demonstrably beyond his means had opened the former minister to the charge that he had lost the sense of himself and of his political roots.
That could find a wider political resonance in the Labour heart-lands. Mr Blair reluctantly accepted Mr Mandelson's resignation on the grounds that "we can't be like the last lot".
With crucial Scottish, Welsh and European elections only months away, challenging and arresting any such perception suddenly became Mr Blair's number one priority. That glorious honeymoon seemed but a distant memory.