John Downey, 62, had been charged with the murders of four soldiers after his arrest at Gatwick Airport last year.
He was detained because his name was on the UK's most wanted list - but in 2007, despite the outstanding warrant, he had been granted an immunity deal.
Judge Mr Justice Sweeney branded the blunder by the PSNI a "catastrophic error".
Chief Constable Matt Baggott has said that the force accepts "full responsibility" for the failures and that the matter will be referred to the Police Ombudsman.
I wish to apologise to the families of the victims and survivors of the Hyde Park atrocity. I deeply regret these failings which should not have happened.
Chief Constable Matt Baggott, PSNI
The case was thrown out on Friday, but that can only be reported now as the prosecution has confirmed it does not intend to challenge the ruling.
The four members of the Royal Household Cavalry killed as they travelled to Buckingham Palace from their barracks were Roy Bright, Anthony "Denis" Daly, Simon Tipper and Jeffrey Young.
Their families have issued a statement describing their devastation at the development.
"This news has left us all feeling devastatingly let down, even more so when the monumental blunder behind this judgment lies at the feet of the Police Service of Northern Ireland," they said.
"The end result is that the opportunity for the full chain of those terrible events will never be put in the public domain for justice to be seen to be done."
Adding that the grieving "never stops" for them, the families said they would have to "learn to live with the knowledge that justice will now never be seen to be done".
The torment for the families will be ongoing knowing that John Downey will be returning to his family and life will be normal for him.
John Downey had strenuously denied the allegations against him regarding the bomb attack.
As well as the four soldiers, it also killed seven horses and further injured a total of 31 people - both civilians and Metropolitan Police officers.
A statement from the Met said: "The strength and dignity the families have continued to show has been remarkable and we will continue to support them during this extremely difficult time."
Northern Ireland Secretary of State Theresa Villiers has confirmed that efforts are underway to identify "whether there are other cases similar to that of Mr Downey".
She added: "It is right that time is taken to consider the full implications of this judgment.
"The PSNI will wish to reflect on lessons learned from this case and the circumstances that led to the serious error which occurred."
The current president of the Association of Chief Police Officers, Sir Hugh Orde, was Chief Constable in Northern Ireland between 2002 and 2009.
He accepts the findings of the court in relation to what he called "a long and complex chain of events stretching back over 30 years, including decisions made in the context of a delicate and, at times, turbulent peace process".
Sir Hugh added: "It is a matter of great personal regret that a crucial oversight was made by a senior officer which resulted in erroneous information being sent to Mr Downey by the Northern Ireland Office and thus prejudicing the current indictment."
If a force under my command has failed them (the victims’ families), as it seems it did, then I apologise to them unreservedly.
Sir Hugh Orde
DUP First Minister Peter Robinson branded it "an outrage and a dark day", insisting that there should not be "a sell-by date" for justice.
"It is little wonder that some have lost faith in our justice system," he said.
"Mr Downey was being tried for one of the most heinous atrocities of the Troubles, but has now invoked a get-out-of-jail-free card which he and his cohorts were handed by Tony Blair's government."
Mr Robinson added that the letters issued in some cases were "ill-conceived", stating: "No one should be above the law and everyone should be equal under the law - however, this short-sighted and irresponsible process has now denied justice to victims of PIRA terrorism."
Sinn Féin MP Francie Molloy said that his party's position that John Downey should not be prosecuted had been "vindicated".
He added: "The arrest and charging by the British police of John Downey was a clear breach of commitments given by the British government at Weston Park and in subsequent negotiations.
"Following the Good Friday Agreement, both the British and Irish governments accepted that the issue of those defined as OTRs (on-the-runs) was an anomaly and the two governments committed to resolve the issue.
"A process was put in place to deal with outstanding cases including that of John Downey. Sinn Féin made it clear from the outset that the decision to prosecute John Downey was the wrong one."
The case remains open and any further information that comes to light will be fully investigated.
UUP Justice spokesman Tom Elliott branded the immunity assurances handed out "a disgrace".
He added: "The scale of this is breath-taking. We are not talking about an isolated case, but 187 letters issued.
"John Downey was wanted by the Metropolitan Police in connection with a brutal and savage crime. No piece of paper should be allowed to shield him from justice."
In confirming that the Crown would not appeal the decision to throw out the case, prosecution QC Brian Altman said: "The Attorney General and the CPS stand by the decision to bring this prosecution and believe it was right to do so, despite the existence of the letter received by Mr Downey in July 2007 - the terms and effect of which have now been tested before the court in public."
He explained that the Attorney General and the CPS had considered the judgment with great care and accepted that "there are no grounds upon which the ruling may be challenged".
The judge made an order that the indictment be stayed.
He added that the order had to be qualified because it had to be borne in mind that it was based on the terms of the letter and that, in those circumstances, there could be "an application in relation to the stay in the future".