News of the World 'paid royal police officer'
Evidence has been found suggesting the News of the World paid a royal protection officer for contact details of senior members of the Royal Family.
E-mails include requests for sums of about £1,000 for the details, BBC business editor Robert Peston reports.
The Metropolitan Police responded by saying the disclosures were part of a deliberate campaign to undermine its inquiry into alleged illegal payments.
The force said it was "extremely concerned and disappointed".
The prime minister described the allegations as "appalling".
"It's a dereliction of their duty, a dereliction of service, and we need to get to the bottom of it if that is true," David Cameron said.
The evidence was contained in e-mails uncovered by NoW publisher, News International, in 2007, but not given to the Metropolitan Police until June this year, the BBC has learned.
In one of the e-mails Clive Goodman, the paper's disgraced former royal editor, was requesting cash from the newspaper's then editor, Andy Coulson, BBC business editor Robert Peston said.
The cash was to buy a confidential directory of the royal family's landline telephone numbers, and all the phone numbers - including mobiles - of the household staff.
The e-mail implies that a police officer in royal protection had stolen the directory, which is known as the Green Book, and wanted £1,000 for it.
The implication of the e-mails is that the News of the World had bought the Green Book on at least one previous occasion, our business editor said.
The e-mails also suggest that the newspaper had police contacts in a number of royal palaces, and had bought information from several of them.
Mr Coulson, who was editor of the News of the World from 2003 to 2007, has denied any knowledge of phone hacking and corruption.
Mr Cameron said he had had no information to suggest Mr Coulson knew about phone hacking, and if he had done he would not have employed him.
He said he gave the former NoW editor a second chance in "good faith".
"If it turned out that those assurances were untrue, I would be incredibly angry and incredibly let down and the first person to put my hand up and point out that this brings about a different situation," said Mr Cameron.
A source told our editor: "There was clear evidence from the e-mails that the security of the royal family was being put at risk. I was profoundly shocked when I saw them."
The source added that the e-mails were unambiguous signs of criminal activity at the News of the World.
"It is quite astonishing that these e-mails were not handed to the police for investigation when they were first found in 2007," he said.
When News International reviewed these e-mails this year, under new management, they appointed the former director of public prosecutions Lord Ken Macdonald to assess their content.
He found evidence of very serious criminal activity, our business editor said, and advised News International to pass the e-mails on to investigating officer Cressida Dick at Scotland Yard.
James Murdoch, News International's chairman, has said he was not in the picture about the full extent of wrongdoing at NoW until recently, and News International has denied he had any prior knowledge of the e-mails.
Former Liberal Democrat leader, Ming Campbell, said it was a worrying development which "must inevitably raise questions as to whether or not at any stage the safety of the royal family was prejudiced".
In a separate development, the Guardian website reported that police had warned Buckingham Palace they had evidence that the Prince of Wales and the Duchess of Cornwall may have had their voicemails intercepted.
It said a palace source had told the paper the couple were likely targets of private investigator Glenn Mulcaire, who was jailed in 2007 along with NoW royal editor Clive Goodman for phone hacking carried out for NoW.
A spokesman for Buckingham Palace said it would not comment on an ongoing police investigation.