After the Soviets were chased out in 1989, the Kharotis gained the upper hand because one of their tribesmen, Gulbuddin Hekmatyar, rose to become prime minister, backed by Pakistan with guns and money. In 1995 the Wazirs sided with the Taliban, who chased away Hekmatyar, and they rose to power together. Then along came the Americans, and the Kharotis cleverly sided with them, handing over a "terrorist" to curry favor.

"They gave the Americans an Uzbek captive," says one Wazir scornfully, as murmurs of disgust fill the crowded room. After that the Kharotis were trusted by the U.S. military and given jobs as militiamen and workers at the local American firebase at Shkin. And, he adds, the Kharotis used the Americans to take revenge against the Wazirs. The Wazirs, he says, had no choice but to side with al Qaeda and the Taliban, who gave them weapons to attack the Kharotis as long as they killed a few U.S. soldiers in the bargain.

As we drive away from the jirga at dusk, we come across a 15-vehicle U.S. armed convoy. "Hey! How's it going?" I yell out. But in my baggy shalwar kameez and turban, I get a chilly response. To them I look like a Wazir, and the words coming out of my mouth may not even register as English. The convoy halts at a crossroads, and the vehicles remind me of a wolf pack, sniffing the night wind for prey, before they rumble off into Wazir territory.

Back at Gul Mohammad's house for the night, I wander out into the courtyard to call my wife on a satellite telephone. Suddenly, I hear a Predator drone circling overhead, and I wonder, with horror, whether I had summoned it with my phone call. I cut off my wife abruptly and pray that I hadn't called a missile with bin Laden's name on it down on our host's farmhouse. After a few long minutes the Predator moves on across the field of stars, and I fall into a restless sleep.

The next day, as Reza and I approach the U.S. firebase at Shkin, the Kharoti militiamen who guard it eye us and our Wazir companions with open hostility, but they finally let the two of us—but not our bodyguards—through the giant coils of razor wire.

Inside I reel with culture shock. Rap music pours from a sandbagged gym where soldiers of the Second Battalion, 27th Infantry Regiment, are lifting weights, which clang along with the music. Inside the chow hall all the soldiers are eating next to their guns, watching baseball on a giant TV screen. A few Kharotis mill around the kitchen, wearing plastic shower caps for hygiene instead of turbans. Later Reza points out a dozen tribesmen who have gathered, gape-jawed, to watch a woman soldier sawing a plank. She is wearing gym shorts and a T-shirt. "This is very strange to us," remarks one worker.

Reza asks several Kharoti workers if they are still loyal to their chieftain, Hekmatyar, who is high on the U.S. most wanted list in Afghanistan, along with bin Laden and Mullah Omar. To a man, they reply yes. Worrying news. For now, Hekmatyar may want his men inside the camp spying on the Americans and collecting a paycheck. But the day may come when he tells his Kharotis to rise against the Americans if for no other reason than they were forced to parade around in plastic shower caps or watch women in shorts do woodwork.

The Shkin camp commander is Capt. Tommy Cardone, 32, from Memphis, Tennessee. He's quick-witted and energetic, seeming to run on five-times-normal voltage. Captain Cardone came to Shkin thinking that his job would be chasing al Qaeda up and down mountains. He still does that. But to hunt down his enemies, Cardone has to first know where they're hiding, and that sort of intelligence comes only with understanding the Pashtun tribes and their complex weave of loyalties and vendettas.

Next morning Captain Cardone takes us out on patrol. The mission is to visit a few villages, give away a few generators, and also to see if the patrol can prompt al Qaeda to ambush us. If that happens, the convoy, backed by air support, will respond with scorching firepower, at least in theory. I climb into the back of a Humvee, and off we go. As we rumble through one village, I notice a guy on a rooftop using a mirror to signal our presence to others—perhaps Taliban—on a distant hilltop ahead of us. As we pass it, I brace for an attack. When nothing happens, the soldiers are disappointed; I start to breathe again.

An hour later, over brackish green tea with village elders, Cardone explains that U.S. troops in Afghanistan are more sensitive now about Pashtun culture. During house searches the men of the family are given time to cloister their women in one room before the soldiers enter. Nakedness is a great shame for the Pashtun, he explains, so no man is strip-searched in public by the soldiers. Gifts help too, and the generators are a big hit. One village elder hugs Cardone and says, "I would die for the U.S. soldiers now."

"Let's hope that isn't necessary," Cardone replies. A few miles away, at a village where the U.S. gave away generators and a tractor, the Taliban came down out of the hills and warned that from then on, anyone who took American gifts would be shot dead.

Slowly, the Americans are making inroads in Bin Ladenstan. Intelligence on al Qaeda has improved, and in one village square Captain Cardone noticed a change in the scenery: Before, the walls of a tea shop had a primitive drawing of al Qaeda stick people shooting at helicopters. Now those figures of gunmen were erased, and in the drawing the U.S. helicopters were flying unharmed over the land of the Pashtun. It's a happy picture. But among these wild-hearted warriors, and with the world's most elusive ghost still at large, it may be nothing more than an illusion.