The Commons Home Affairs select committee has said the Home Office agency's project appears to be in breach of European treaty rules allowing travel between EU countries on production of a valid identity document, except in exceptional circumstances.
In a highly critical report published on 18 December 2009, it tells the agency to seek an opinion from the European Commission as to the legality of e-Borders' use within Europe, and report back by the end of February. In the meantime, it must put on hold proposals to extend the system to new routes within the EU.
The Home Office responded that the Commission is happy with the legality of the system. "e-Borders is fully compliant with EU law and this has been confirmed by the European Commission today," said minister Phil Woolas.
The £1.2bn system requires transport operators to collect, on UKBA's behalf, a wide range of data including travellers' contact details and itinerary, known to airlines as Passenger Name Records. The committee adds that requiring such data is also problematic under the national data protection laws some European countries', such as Germany.
Committee chairman Keith Vaz said the UKBA had made some progress on technical problems with e-Borders. "But the major stumbling block, and a very disappointing oversight, is that we are sure that what the programme requires will be illegal under the EU Treaty.
"Until this legality is resolved UKBA must just halt any further work to 'go live' on intra-EU routes. We cannot have another massive IT project which flounders or is even abandoned at huge cost to the taxpayer. It is simply unacceptable," he added.
The report says the committee had asked UKBA chief executive Lin Homer in July to provide transport operators with a letter from the European Commission confirming the programme's legality. "We are still waiting," it notes.
The report also criticises e-Borders for changing its demands on travel operators, which had meant some airlines changing their systems for one set of requirements, then having to alter them again as the government changed its mind.
It expresses serious concerns about the scheme's extension to boat and rail travel, noting that neither sector collects as much data as airlines. The Chamber of Shipping told the committee that it fears delays and congestion at ports as a result of data being demanded of all passengers.
On rail, the committee says it is possible to buy Eurostar tickets at a wide range of locations which cannot record passport details and other data, and that the situation is further confused as passengers can leave and join trains at intermediate stops.
"UKBA cannot impose one-size-fits-all requirements on such different sectors as planes, ferries and railways," the MPs said. "It would be more productive if, instead of trying to do so, they adapted their requirements more closely to how each sector actually operates."
Conservative shadow immigration minister Damian Green commented: "It beggars belief that after so many years of pursuing this project the government still isn't sure whether it is even legal. Over a billion pounds of taxpayers' money has been spent on e-Borders and yet many of the most basic problems have not been resolved."
* Update: the government is reported to have made the e-Borders scheme voluntary for those travelling from elsewhere in Europe, to satisfy the European Commission of its legality, according to reports in both The Times and The Telegraph.
According to a letter from Jonathan Faull, director general of the European Commission's Justice, Freedom and Security directorate, passengers must be told in advance that they do not need to provide the UK with data in advance of travel. "Passengers who are EU citizens or their family members will not be refused entry/exit or incur sanctions in any way on the basis that their passenger data is unavailable to the UK authorities for whatever reason," it read, according The Telegraph.
The Home Office refused to comment beyond its earlier statement. The European Commission confirmed that discussions have taken place over the last few months, and it is now happy with e-Borders's legality based on the UK's latest commitments, but said it would not be releasing Faull's letter.
