It is perhaps too early to speak of an al-Qaeda Mark-II - but as the Madrid attacks demonstrate, the phenomenon is changing.
The al-Qaeda leadership - Osama Bin Laden and his chief lieutenants, many of whom owe their close ties to the Afghan resistance against Soviet occupation - are under huge pressure.
Al-Qaeda has been blamed for a string of attacks since 2001
Several senior figures have been captured or killed.
But counter-terrorism experts are convinced that the al-Qaeda threat has not so much gone away as changed its form.
Last week's bomb attacks in Madrid came as troops from the United States and Pakistan were stepping up preparations for an offensive on both sides of the Afghan frontier.
A new operation which is just under way, code-named Mountain Storm, is intended to disrupt Osama Bin Laden's network and perhaps even target the al-Qaeda leader himself.
But the juxtaposition of these two events tells us something of the developing challenge that Europe and the US now face.
In the wake of the 11 September 2001 attacks, the US media was quick to personalise the anti-terrorist struggle.
The face of Osama Bin Laden became the face of the enemy.
In terms of a traditional counter-terrorism operation, the US had done reasonably well.
Several of Osama Bin Laden's closest associates have been killed or captured, including key planners of the 11 September attacks and the men thought to be behind the attack on the USS Cole.
The organisation's logistical base in Afghanistan has been largely destroyed and the Taliban regime that backed it toppled.
Now Osama Bin Laden himself may be in America's sights - but the terror threat has not gone away.
Switch in tactics
The Madrid attacks - if indeed the work of an Islamic group - illustrate some worrying new developments.
New militants, though inspired by al-Qaeda, can often act alone
For one thing they appear not to have been suicide bombings - until now the preferred al-Qaeda method.
Explosives were simply left in bags on the trains.
The perpetrators are thus alive to carry out future attacks.
But of even greater concern is that the US intelligence agencies say they picked up none of the communications "chatter" prior to the bombings that would have given warning that a major attack was imminent.
This suggests a more locally-planned attack - one that was not guided or instigated from afar.
The timing, too, shows a new sophistication - not just an attempt to cause mass casualties, but an attempt to cause them at a moment of maximum political sensitivity, almost on the eve of the Spanish general election.
Of course, it may well have been the Spanish government's handling of the aftermath of the explosions that was as much responsible for its defeat as the bombings themselves.
'Infected' and independent
Giving evidence last month on Capitol Hill, the head of the US Central Intelligence Agency, George Tenet, noted how "successive blows to al-Qaeda's central leadership" had transformed the organisation into a loose collection of regional networks that operate more autonomously.
The hunt goes on in Afghanistan - but has al-Qaeda changed address?
He said a number of smaller international extremist Sunni groups have undoubtedly benefited from their al-Qaeda links.
Many al-Qaeda experts have always stressed this aspect of al-Qaeda's influence.
They have long seen Osama Bin Laden more as a figurehead, an inspiration to "a global movement infected by al-Qaeda's radical agenda" as Mr Tenet put it.
Just such a group may have been behind the Madrid bombings.
But they may largely be independent of direct al-Qaeda control and so the growing military pressure in the border-lands between Afghanistan and Pakistan may do little to decrease fears of further terror attacks in Europe.