“Coalition forces have recovered what we believe are the remains of the soldiers,” Major-General William Caldwell, a US military spokesman, told reporters. He refused to comment on how the young men abducted at a roadblock near Yusufiyah last Friday night had been killed.

An internet statement said that the new head of al-Qaeda in Iraq had “slit the throats” of the two men. It used the word “slaughter”.

“God Almighty has graced the leader Abu Hamza alMuhajir . . . with the implementation of the sentence,” said a statement from the Mujahidin Shura Council, a rebel association that includes al-Qaeda in Iraq. If true, the act would be a brazen act by the successor to al-Qaeda’s former leader, Abu Musab al-Zarqawi, who was killed in a US airstrike two weeks ago.

The council, which includes al-Qaeda, claimed on Monday that it had kidnapped the two men. The statement yesterday said: “We have carried out God’s verdict by slaughtering the two captured crusaders.”

President Talabani of Iraq told The Times in an interview that he was sure that al-Qaeda was responsible for the deaths of Privates Thomas Lowell Tucker, 25, and Kristian Menchaca, 23.

“Yes I think so. They are committed to do such kinds of crimes. I imagine that al-Qaeda killed them,” he said.

Major-General Abdul Aziz Muhammad, an Iraqi Defence Ministry official, told reporters earlier that the bodies showed signs of “barbaric torture”.

General Caldwell said an intensive Iraqi-US rescue mission, which deployed 8,000 troops and helicopters, boats, divers and aircraft, located the bodies on Monday night dumped at an electrical plant near Yusufiyah, the same area where they went missing on Friday night.

“The remains were located by Coalition forces acting on a tip from an Iraqi civilian. The individual also warned the forces to be alert for possible explosive devices,” the US military said in a statement.

“Coalition forces had to carefully manoeuver their way through numerous improvised explosive devices leading up to and around the site. Insurgents attempting to inflict additional casualties had placed IEDs around the bodies. During the course of the search, one Coalition force soldier was killed and 12 were wounded.”

The soldiers had disappeared in an area known in Iraq as the Triangle of Death for its killings and kidnappings.

Meanwhile, General Caldwell said that a US airstrike on a fleeing vehicle killed a senior al-Qaeda leader from Iraq on Friday in the same area where the two American soldiers went missing.

US forces had been tracking Mansur al-Mashhadani, identified as the top al-Qaeda religious leader in the country. General Caldwell said: “We do know that Sheikh Mansur was a key leader in al-Qaeda in Iraq with excellent religious, military and leadership credentials within that organisation.”

He described him as al- Zarqawi’s right-hand man and a liaison between al-Qaeda and tribes in the restive area south of Baghdad. “He was tied to the senior leadership, including having relationships with both Zarqawi and al-Masri,” General Caldwell said, referring to Abu Ayub al-Masri, whom the US military claim to be al-Zarqawi’s successor and the same man as Abu Hamza al-Muhajir. The discovery of the bodies brought criticism of the war from relatives of the soldiers and came on a day when, despite the announcement of pullout plans, violence scarred the country.

In Baghdad, nine people died in bombings despite a new security plan for the capital. The US military also announced that it had killed 15 gunmen linked with al-Qaeda in raids north of the capital.

• Abu Musab al-Zarqawi will be buried in an unmarked grave in Iraq, the country he terrorised for three years, because his native Jordan has refused to take his remains.

  “Zarqawi’s body will be buried in an unidentified site with no mark,” Mouwaffak al-Rubaie, the Iraqi National Security Adviser, told The Times. The remains have been kept near Baghdad airport.

Times Recommends

• No cause for celebration in crushed Sarajevo
• Jazz funeral for the final victims of Katrina
• French fined for 'insulting' civil servants