Prominent politicians chastised the company and Ms. Brooks, and Ford Motor Company suspended advertising in The News of the World, the tabloid that has faced a long-running scandal over the widespread interception of voice mail messages of celebrities and other public figures.
Ed Miliband, leader of the opposition Labour Party, said Tuesday that Ms. Brooks should "consider her conscience and consider her position" after the disclosures.
"It wasn't a rogue reporter," Mr. Miliband said. "It wasn't just one individual. This was a systematic series of things that happened, and what I want from executives at News International is people to start taking responsibility for this." News International is the News Corporation's British newspaper division, and Ms. Brooks is now its chief executive.
Prime Minister David Cameron took time out from a visit to British troops in Afghanistan to lament what he called a "truly dreadful situation." The police, he added, "should investigate this without any fear, without any favor, without any worry about where the evidence should lead them."
Adding to the pressure, Ford Motor Company said it was suspending advertising until the newspaper concluded its investigation into the episode. "We are awaiting an outcome from The News of the World investigation and expect a speedy and decisive response," Ford said in a statement released to news agencies. Under an onslaught of Twitter messages demanding a boycott of the paper, several other companies said they were reviewing their advertising policies.
Late Tuesday, The Guardian reported that the police would review every highly publicized murder, kidnapping or assault involving a child since 2001 for evidence of phone hacking. That would include the notorious case of Madeleine McCann, the 3-year-old who disappeared while her family was on vacation in Portugal in 2007.
In another development, Channel 4 reported on Tuesday that Ms. Brooks met with the police in 2002 over accusations that the tabloid had placed a senior Metropolitan police detective under surveillance.
The detective was investigating the murder of a private investigator who had been found dead with an ax buried in the back of his head. The chief suspect at the time was the dead man's business partner, a private investigator who earned a six-figure salary supplying The News of the World with confidential information. Nothing apparently came of the inquiry into The News of the World's surveillance.
Scotland Yard detectives were also investigating whether the phones of some families of victims of the bombings of three London subway trains and a double-decker bus in July 2005 had also been hacked, The Telegraph reported.
In his remarks, Mr. Cameron did not mention Ms. Brooks, but his comments were notable because, like other British politicians, he has cultivated social connections with News Corporation executives like Ms. Brooks and Rupert Murdoch, the chief executive of the company. Mr. Cameron, along with Gordon Brown, the Labour prime minister at the time, was a guest at the reception following Ms. Brooks's marriage to her second husband, Charlie Brooks, in 2009.
Ms. Brooks vowed to "pursue the facts with vigor and integrity," saying she had no intention of quitting.
"I am aware of the speculation about my position," she said in a memo to News International employees. "Therefore it is important you all know that as chief executive, I am determined to lead the company to ensure we do the right thing and resolve these serious issues."
The allegations center on one of the most sensational Fleet Street stories of the last decade, the disappearance of Milly Dowler in 2002. The case was the subject of many tabloid front pages over the last decade, culminating last month in the conviction of Levi Bellfield, a former nightclub doorman, on charges of kidnapping and murder.
The allegation that investigators working for The News of the World may have had ordinary people like the Dowlers, not just celebrities, in their sights has raised the level of alarm in Britain over tabloid newspaper excesses.
"The Milly Dowler story has taken this from an issue for people who are concerned about media ethics to one that is of broader concern to the general public," said Tim Luckhurst, a journalism professor at the University of Kent. "News Corporation thought they could put a lid on this, and this has blown the lid right off."
In a statement, Mr. Lewis called the newspaper's actions "heinous" and "despicable," and said the Dowler family had suffered "distress heaped upon tragedy" upon learning that The News of the World "had no humanity at such a terrible time."
Public revulsion over the affair has been so intense that a private investigator at the center of the phone hacking, Glenn Mulcaire, felt compelled to provide a statement to The Guardian on Tuesday evening, his first public comment in the five years since the scandal broke. In it he apologized "to anybody who was hurt or upset," and said he was speaking out because of the "vilification" he and his family had been subjected to in the past 24 hours.
Mr. Mulcaire, who worked for The News of the World and served prison time for his role in hacking the phones of members of the royal family, blamed "relentless pressure" at the paper for his mistakes, saying "there was a constant demand for results."
He added: "I knew what we did pushed the limits ethically. But, at the time, I didn't understand that I had broken the law at all. A lot of information I obtained was simply tittle-tattle, of no great importance to anyone, but sometimes what I did was for what I thought was the greater good, to carry out investigative journalism."
If Mr. Lewis's accusations about hacking during the Dowler case prove accurate, it would mean either that Ms. Brooks had no idea how the paper she edited was obtaining information about the Dowler family for its articles, or that she knew about the hacking and allowed it.
Ms. Brooks, in her memo, did not deny the allegations, but said she had had no knowledge of phone hacking on her watch. "I hope that you all realize it is inconceivable that I knew or worse, sanctioned these appalling allegations," she said.
The scandal has already claimed the job of one former high-ranking News Corporation official, Andy Coulson, who was Ms. Brooks's deputy at The News of the World in 2002 and who later moved into the top editor's role.
The allegations in the Dowler case appeared as the British government weighs an important business matter affecting News Corporation: its proposed acquisition of British Sky Broadcasting, a pay-TV company in which it is already the largest shareholder. Government officials have indicated that they intend to approve the plan, and say the Dowler case allegations should have no bearing on the matter.
"It really doesn't have anything to do with the hacking inquiry," Vince Cable, the business secretary, said on BBC television.
There has long been speculation that other British papers may have engaged in similar tactics. So widespread was the practice that even Ms. Brooks, in a surprising twist, is apparently among the victims of phone hacking.
News International said last month that Ms. Brooks had been informed by the police that her voice mail messages had been intercepted by Mr. Mulcaire.
The hacking apparently took place around 2005, when Ms. Brooks was editor of another News Corporation tabloid, The Sun, and when there was considerable interest in her personal life. In November 2005, she was detained by the police in a domestic dispute with a British actor named Ross Kemp, her husband at the time. Ms. Brooks, then known under her maiden name, Rebekah Wade, was not charged, and the two later divorced.
Get the latest election news, live updates and election schedule for Lok Sabha Elections 2019 on ndtv.com/elections. Like us on Facebook or follow us on Twitter and Instagram for updates from each of the 543 parliamentary seats for the 2019 Indian general elections.