"We are entering a new era of the relations between Libya and the EU," said EU foreign affairs and external relations commissioner Benita Ferrero-Waldner.

She explained that the release of the medics was a condition for normalisation of relations with the energy-rich north-African country, which has been strained for the past 20 years over issues such as terrorism.

The medics were sentenced to death on two occasions and later to life imprisonment for allegedly having infected over 400 children with the HIV virus at a Libyan hospital in Benghazi.

They have denied the charges saying they were tortured to confess and that the tragedy was caused by bad hygiene at the Benghazi hospital. So far, more than 50 of the children have died as a result of the virus.

The medics – including the Palestinian doctor who now has a Bulgarian citizenship - were pardoned on their arrival to Bulgaria by the country's president.

The commissioner – who has been working on securing the medics release since she took up her post as commissioner in 2005, said she felt relieved and happy, adding that there were sometimes "very sad moments" where everything looked bleak.

Ms Ferrero-Waldner said she had signed a memorandum of understanding with the Libyan authorities, which mapped out ways of upgrading EU-Libyan ties saying relations will eventually go "into some sort of specific…agreement."

With the new relationship, Libya can look forward to better access to the EU market for Libyan goods, funding for restoration of potential tourist sites, better visa facilitation for Libyans, scholarships for students and help to deal with the illegal immigration going through Libya towards Europe.

The commissioner also pointed out that the EU executive would negotiate such an accord with Libya on the basis of a mandate or negotiating guidelines set by EU governments.

The only one without a deal

Libya is the only country in the region that is not a member of the bloc's 11-year old Euro-Mediterranean - which covers all other countries around the sea – or in the EU's ‘European Neighbourhood Policy' under which states on the bloc's southern and eastern borders receive financial aid for political and economic reform.

Relations between Brussels and Tripoli improved slowly after Libya abandoned a plan for nuclear weapons and in 2003 handed over two nationals accused for the 1988 bombing of an American Airlines plane over Lockerbie, Scotland.

French president Nicolas Sarkozy will head for Libya on Wednesday (25 July) together with his foreign affairs minister Bernard Kouchner to meet with Libyan leader Moammar Gadhafi.

The aim is "to help Libya reintegrate into the international community," he said at a conference in Paris on Tuesday.

What about human rights?

However, not all agree with the sudden improved relation with Libya, with human rights in the country still an issue of concern.

UK centre-right MEP Geoffrey Van Orden, who has been campaigning for the nurses' release, said in a statement on Tuesday that he was "overjoyed" that the torment of the Bulgarian nurses and Palestinian doctor was over.

"In the euphoria we should not forget that the nurses should never have been imprisoned in the first place. Their release," he said, "has involved transfer of enormous sums of money to the Libyans".

He said the release was based on a series of deals which provide medical assistance for Libya's infected children and one million US dollars in compensation to each of the more than 400 affected families.

"I am very dubious about the proposed 'closer EU ties' with a country that conducts itself in such a way. What signal does this send?"

"If anything, the Libyan authorities should be compensating the nurses for their appalling ordeal. We should not be giving credit to Gaddafi's political opportunism and Libya's backward judicial system," he stated.