One of my self-imposed missions in dust-caked Grozny had been to find the shop that supplies the meat for the lions, panthers and leopards that populate the private zoo of warlord-turned-President Ramzan Kadyrov.

But the capital of Chechnya is in the midst of a pharaonic reconstruction and even the locals are getting lost. One engineer holed up in my bedbug-infected hotel, the Kavkaz, had shiny eyes when he talked of the building work. It was, he said, comparable to the great socialist projects, the dams and people’s palaces, the rebirth of Minsk, smashed by war.

“Forget the meat idea,” said my guide Sayed Magomed, a 23-year-old engineering student. “He gets sheep from a farm in eastern Chechnya and slaughters them himself - he doesn’t need anyone to do that for him.” Sayed is still fired with adrenalin after a Saturday morning spent on the latest Grozny craze, paintballing, a more or less harmless postmodern form of partisan warfare: you stalk, you shoot and no one gets killed. It could catch on.

“You mustn’t write off Kadyrov just because he used to kill people in the war against the Russians. He is a strong man, a modern leader,” he said.

He is certainly a very visible leader. All along the M29 from Ingushetia his image appears at petrol stations, on every telegraph pole. Sometimes he smiles, usually not. Rarely if ever do the posters show his butcher’s hands, muscular fingers and spatulate thumbs.

Over the past few months the region of Ingushetia has suffered a rising wave of attacks on security services and officials. On Thursday gunmen fired on a military convoy, killing two soldiers, and the head of a district police division died in a separate gun attack on his car. A soldier was also killed in the Shali region of Chechnya by three gunmen who shot him in the street. Responsibility for the rising tide of killings is unknown. Observers attribute them variously to criminals, Islamist fighters and opponents of the republic’s President, Murat Zyazikov.

In the first Chechen war in the early 1990s Mr Kadyrov fought against the Russians. In the second Chechen war, Vladimir Putin’s war, Mr Kadyrov changed sides. The deal now is that this recently minted Russia loyalist receives Moscow’s financial support in reconstructing a city that they largely destroyed. And he gets a slice of the lucrative contracts.

In return, the Chechen separatist agenda has been ditched. Part of the theatre of reconciliation is that Mr Kadyrov makes flamboyant, perhaps ironic, gestures towards the Russians. The other day he named a Grozny street after a Russian general who had once called for the public execution of Chechens. The general had died in a plane crash some days earlier. A few years back Mr Kadyrov would have hung the officer from a lamppost.

For the Kremlin, this is as close as it comes to stability in the Caucasus. Nobody knows how long it will last. Mr Kadyrov sees one east Chechen family, the Yamadayev clan, as a threat to his rule. Like him, they were warlords who changed sides; like him they are attracted by the financial rewards either from reconstruction, or the advantages of the Russian authorities turning a blind eye to their criminal activities. One clan member, Sulim Yamadayev, helped out the Russians by leading his ruthless and battle-hardened Vostok Battalion against the Georgians in August. His big brother Ruslan was gunned down in the Moscow rush-hour traffic. Mr Kadyrov is being blamed and it seems safe to assume that there will be some bloody vendetta killings in the coming weeks.

The Moscow shooting reminded the Kremlin that Chechnya has long since stopped being on the imperial periphery. Feuds in the North Caucasus translate quickly into problems at the very heart of empire.

Dagestan, to the east, could be the first to implode. The clerics there consider themselves to be the spearhead of Sufi Islam in the region, the stamping ground of the 19th-century rebel hero, the red-bearded Imam Shamil, who held out for decades against tsarist troops. Now it is the classic Caucasus hotpot: corrupt police, organised crime, rival Islamic groups and the often brutal intervention of Russian special forces. Local Dagestan police - unless bribed to turn a blind eye - identify youths as Islamists and pass on the information to the Russians, who send in snatch squads from their bases in Chechnya. They frequently disappear. Meanwhile, Dagestani rebel leaders take hostages and sell them on to gangs in Chechnya. They are enslaved in the mountains, held in dark damp pits until a ransom is paid.

Nothing, however, excites a Chechen taxi driver more than a well-paid challenge. We stray briefly from the M29 because he has caught wind of trouble but we rejoin the road at the border crossing. The Russian troops are out in force but let us through. A bottle of brandy is offered up. Ten kilometres into Dagestan we are stopped by a bunch of youths. They wave guns, scream orders.

The youngest, unbearded, is delegated to talk to us. They want cash. The Chechen driver is inclined to drive through them. I, on the other hand, would like to live a little longer. Fifty dollars is handed over, barely adequate to pay for breakfast in a Moscow hotel but enough surely to have a good time in a Dagestani mountain village. The boy demands my wallet.

“Have this,” I tell him, “it’s a credit card.” I give him a green and black Waterstone’s loyalty card.

“Credit?” he asks. I nod. The boy moves towards his comrades, to inform them of his booty. On the way he accidentally pulls the trigger of his unsecured Kalashnikov and the loud report, the spray of street grit, seem to frighten them even more than it does me. The Chechen grabs the moment and spurs the car forward, like a Terek Cossack. I lie down in the back, just in case, but nothing happens. Perhaps they are already planning a visit to Waterstone’s.

“That kid has got a thing or two to learn,” says the driver, unflustered.

No more shots were fired on the M29 that night.

Times Recommends

• Violent video games won’t corrupt
• Pope Benedict XVI: Alma Mater
• Chávez should know what’s good for him