29,000 asylum cases still unresolved from 2007, say MPs
The Home Office has "failed to deal" with the UK's backlog of asylum cases, with 29,000 applications dating back at least seven years still waiting to be resolved, MPs have warned.
The Public Accounts Committee said 11,000 of those applicants had not even received an initial decision on whether they could remain in the country.
Contact was lost with 50,000 people refused the right to stay, it added.
The government said it was "addressing the backlogs inherited" in 2010.
During Prime Minister's Questions, Labour leader Ed Miliband told David Cameron to "apologise" for his record on immigration, adding: "You're not making it right. You're making it worse."
But Mr Cameron replied that the coalition was "clearing up a shocking shambles and mess left by the last Labour government".
The government overhauled the UK's immigration and asylum operations in 2013 after a series of controversies, including a 2011 row over the relaxation of passport checks.
Home Secretary Theresa May scrapped the UK Border Agency and assumed direct executive responsibility for its Border Force enforcement arm.
She also took control of UK Visas and Immigration and Immigration Enforcement, new bodies created as part of the Whitehall restructuring.
In a report analysing the impact of the changes, the cross-party Public Accounts Committee said performance had "held steady" in most areas since the reorganisation but the Home Office had still "failed to deal" with the longstanding asylum backlog.
Analysis by Vicki Young, BBC chief political correspondent
Home Office ministers wryly observe that many of the people they deal with are doing their best to avoid being tracked down, but yet again a picture is being painted of a system that's struggling to cope.
Similar problems dogged the last Labour government and led to the then Home Secretary John Reid describing the immigration and asylum system as unfit for purpose.
Eight years on MPs don't believe things are quite that bad, but many of the problems are depressingly familiar - administrative incompetence and a failure to harness technology to streamline services.
Dealing with a huge backlog was never going to be easy, but now that Theresa May has brought the UK Border Agency back into the Home Office fold it'll fall to her to try to convince the public that the government has control of our borders.
The committee also suggested the Home Office was failing to meet its own targets for processing newer claims, which totalled 16,273 in the first three months of 2014.
It partly attributed this to the UK Border Agency's "botched and ill-judged" decision to downgrade caseworkers working in the area.
Although the decision was subsequently reversed, the committee said it had led to 120 experienced staff leaving, and this - combined with major problems with IT systems - meant the department lacked the data to manage the backlogs and track people through the system.
"It is deeply worrying that the Home Office is not tracking those people whose applications have been rejected to ensure they are removed from the UK," said Margaret Hodge, the Labour MP who chairs the committee.
"At the end of 2013-14, there were over 175,000 people whose application to stay in the UK had been rejected, and they are placed in a migration refusal pool to await removal.
"The number of such cases has not been reduced over time. Some may have left the UK voluntarily but without exit checks it is almost impossible to know."
Mrs Hodge said the Home Office had asked external contractors to check more than 250,000 case records in 2012 and 2013 but they had been unable to contact more than 50,000 people listed, their whereabouts unknown.
She said this "particularly disturbing" matter must be dealt with urgently while the Home Office must ensure it had sufficient staff with the right skills to resolve outstanding claims and prevent backlogs growing.
The Refugee Council warned that people caught up in the asylum system were "living in limbo".
"Behind these statistics are individuals, many of whom will have suffered extreme trauma, forced to live day to day in uncertainty while they await the outcome of what could be a life or death decision," said its head of advocacy, Lisa Doyle.
"It is very important that the Home Office makes decisions in a timely manner, but it's even more important that it gets its decisions right first time."
The Home Office, which published its latest figures on its handling of asylum applications in April, said the committee's figure of 11,000 asylum seekers awaiting an initial decision on whether they could stay in the UK was inaccurate.
Initial decisions had been made in many of the outstanding cases, it said, and officials were now considering further evidence provided by applicants with the aim of doing so by the end of the year.
Analysis by Dominic Casciani, BBC home affairs correspondent
This report gets to the heart of the problem: parts of Britain's immigration system don't have enough of the right staff in the right places, the right IT systems and, most importantly of all, the right data and records to help them do their job.
These kinds of management problems directly lead to casework backlogs, missing foreign offenders and, ultimately, judges rolling their eyes in the face of poor decisions that have affected the lives of ordinary hardworking people.
These broad criticisms are not new. They have been repeatedly made for 15 years.
The coalition has brought the system under direct ministerial control - but improvements have come so slowly that a crack internal team tasked with giving ministers a "single version of the truth" doesn't always know what's going on.
Whoever is in power, it may take years to build a system that commands universal confidence, not least because nobody inside the system can yet be confident that it's working as it should.
The recent increase in asylum claims was due to instability in the Middle East and North Africa, it added, but also to past failings by the Border Agency which had been addressed.
Immigration minister James Brokenshire said: "UKBA was a failing organisation that could not deliver an efficient immigration system for Britain.
"This is why we split it up into three separate divisions to improve focus on their specific roles in delivering a controlled immigration system and bring them under the direct supervision of ministers.
"Turning around years of mismanagement has taken time, but it is now well under way. We have reformed visa routes to make them more resistant to fraud and cancelled failing contracts. And we are addressing the backlogs we inherited."
But shadow home secretary Yvette Cooper said: "This report lays bare how David Cameron's government is presiding over one failure after another in our immigration system.
"Theresa May was very quick to blame the UKBA, but since she took direct control of the border force and immigration system, we have seen backlogs increase sharply and the admission that the Home Office have no idea how many of the 175,000 failed asylum seekers are still here or where 50,000 failed asylum seekers even are."
She added: "David Cameron and Theresa May have failed to deliver on her promise to introduce exit checks, to reduce net migration to the tens of thousands, has cost the taxpayer £1bn on failed IT projects and as the report says introduced no processes to rectify these and other failings."
On Tuesday, Natacha Bouchart, mayor of the northern French port Calais, argued the UK was seen as a "soft touch" by asylum seekers and that its benefits system acted as a "magnet".
Planning minister Nick Boles told Total Politics magazine that people in the UK had a "sense that we don't have that control (over immigration) - and, bluntly, they're right. It's true."