Britain, Italy and Greece on Sunday said that a claim by a Nigerian Islamist group that it had killed seven foreign hostages appeared to be true, while London denied it had sought to stage a rescue.
Restive northern Nigeria has seen scores of people killed from Islamist-linked violence, but the hostage executions marked the deadliest kidnapping targeting foreigners in the region in recent memory.
Islamist group Ansaru said in its statement announcing the deaths on Saturday that it carried out the executions in part because British planes had arrived in Nigeria in recent weeks to attempt a rescue, citing local media reports.
But Britain's defence ministry said there had been no rescue attempt and suggested the planes were in Nigeria to transport troops for the military effort in nearby Mali.
Ansaru on Saturday announced the deaths of all the expatriates abducted from a construction site of Lebanese-owned company Setraco on February 16 in Bauchi state in Nigeria's north.
Ansaru, considered an offshoot of the Nigerian Islamist group Boko Haram, backed up its claim with "screen captures of a forthcoming video showing the dead hostages," SITE Intelligence Group said.
"In the communique, the group stated that the attempts by the British and Nigerian governments to rescue the hostages, and their alleged arrest and killing of people, forced it to carry out the execution," SITE said.
The Ansaru statement referred to local media reports claiming five British planes had arrived in Nigeria last month for a rescue bid.
A spokeswoman for the Ministry of Defence in London denied the British had been involved in a hostage rescue mission.
She pointed to Britain's role in assisting the French and the Nigerians in the operation against Islamists in Mali and said it would "not be too far-fetched" to see planes in the area transporting troops and equipment.
Nigerian police last month said the hostages were four Lebanese, one Briton, a Greek citizen and an Italian. A company official later said the Middle Eastern hostages included two Lebanese and two Syrians.
British Foreign Secretary William Hague said all the hostages were "likely to have been killed" by their captors. He named the British man as construction worker Brendan Vaughan.
-- 'Heinous act' --
"This was an act of cold-blooded murder, which I condemn in the strongest terms," he said, expressing his determination to work with the Nigerian authorities "to hold the perpetrators of this heinous act to account, and to combat the terrorism which so blights the lives of people in northern Nigeria and in the wider region."
The Italian foreign ministry in a statement branded it "a horrific act of terrorism for which there is no explanation except barbaric and blind violence."
"No military intervention to free the hostages was ever attempted by the interested government," it said.
The Greek foreign ministry also said the "available information suggests that the Greek citizen abducted in Nigeria alongside six nationals of other countries is dead."
"Based on the information we have, there was no rescue operation," it added.
Nigerian authorities on Sunday declined comment, while a Setraco official said he was awaiting Nigerian government confirmation before issuing any statement.
In an email statement sent to journalists announcing the kidnapping two days after the abduction, Ansaru said the motives were "the transgressions and atrocities done to the religion of Allah... by the European countries in many places such as Afghanistan and Mali".
Ansaru has been linked to several kidnappings, including the May 2011 abductions of a Briton and an Italian working for a construction firm in Kebbi state, near the border with Niger.
The victims were killed in March 2012 in neighbouring Sokoto state during a botched rescue operation.
It also claimed the December kidnapping of a French engineer in Katsina state, bordering Niger. The victim's whereabouts remain unknown.
Seven members of a French family, including four children, were abducted last month in Cameroon, and Cameroon authorities said they were then taken over the border into restive northeastern Nigeria. Their whereabouts also remain unknown.
Ansaru has appeared to focus specifically on kidnapping foreigners, though it has not been known to have claimed the abduction of the French family. France has blamed Boko Haram for the abduction.
Nigeria is Africa's most populous nation and largest oil producer, roughly divided between a mainly Muslim north and predominantly Christian south.