Tony Blair wrote to then Libyan leader Muammar Gaddafi to thank him for the "excellent co-operation" between the two countries' counter-terrorism agencies at a time when they were allegedly collaborating in efforts to send dissidents back to the North African country.

The letter, written in 2007, addressed "Dear Muammar" and signed "Best wishes yours ever, Tony", was among hundreds of pages of documents recovered from Libyan government offices following the 2011 revolution which ousted the dictator and pieced together by a team of London lawyers who are bringing damages claims on behalf of a dozen Gaddafi opponents who claim they were targeted by the two countries' agencies.

The letter, reported in The Guardian, was written on April 26, 2007, to inform Gaddafi that the UK was about to fail in its attempts to deport two Libyans allegedly linked to an Islamist opposition organisation, the Libyan Islamic Fighting Group (LIFG).

Its existence will re-open questions over the two countries' negotiations over the transfer of the man convicted of the Lockerbie bombing, Abdelbaset Ali Mohmed al Megrahi, since the letter was written just two months before the infamous "deal in the desert meeting between the then PM and Gaddafi.

Officials in Tripoli said at the time they had made it clear that moving Megrahi out of Scotland was the main reason for the discussions, while there were repeated Downing Street protestations that his transfer had always been excluded from the memorandum of understanding now signed by the two countries.

The Whitehall denial then echoed a similar statement of rebuttal in October 2005 by the Foreign Office and the former Scottish Executive, after The Herald had revealed then that secret talks were under way to allow Megrahi to return to a prison in Libya or another north African country.

Mr Blair told Gaddafi in the letter: "I trust that you, and your family, are well.

"With regret, I should let you know that the British government has not been successful in its recent court case here involving deportation to Libya. I am very disappointed by the court's decision."

He added: "I believe it is essential that this decision is not allowed to undermine the effective bilateral co-operation which has developed between the United Kingdom and Libya in recent years.

"We have made such progress. It is important, for the good of both our peoples, that we continue to do so, not least in the crucial area of counter-terrorism."

He added: "I would like to add a personal word of thanks for your assistance in the matter of deportation. That support - and the excellent co-operation of your officials with their British colleagues - is a tribute to the strength of the bilateral relationship which has grown up between the United Kingdom and Libya. As you know, I am determined to see that partnership develop still further."

The relationship between Libya and the UK had thawed following Gaddafi's decision to abandon weapons of mass destruction, and it is known that the two countries had co-operated on intelligence matters.

A spokesman for Mr Blair said: "There is nothing secret about the fact that the UK and the then Libyan government co-operated in the fight against terrorism. It was public. Or that the then Libyan government gave up their chemical and nuclear weapons programme and that this happened in 2003 after negotiation.

"At that time the UK was fighting a serious terrorist threat aimed at its people and its soldiers. None of that means the UK Government accepted or condoned torture."

The Guardian said the papers recovered from Libya were now forming the basis of the damages claim being brought by six Libyan men, the widow of a seventh, and five British citizens of Libyan and Somali origin.

The newspaper said they are bringing claims against the British government on the basis of the recovered documents, alleging false imprisonment, blackmail, misfeasance in public office and conspiracy to assault.