WASHINGTON (Reuters) - Verizon Communications Inc. and BellSouth Corp., facing consumer lawsuits seeking massive damages, have issued carefully worded denials of a report that they turned over millions of customers' calling records to a U.S. spy agency.

USA Today reported last week that the National Security Agency has had access to records of billions of domestic calls and collected tens of millions of telephone records from data provided by BellSouth, Verizon and AT&T Inc..

BellSouth and Verizon denied the part of the USA Today report that said the companies had received a contract from the NSA and that they turned over records. However, Verizon declined to comment on whether it provided access to the NSA.

"One of the most glaring and repeated falsehoods in the media reporting is the assertion that, in the aftermath of the 9/11 attacks, Verizon was approached by NSA and entered into an arrangement to provide the NSA with data from its customers' domestic calls," Verizon said in a statement on Tuesday.

However, "Verizon cannot and will not confirm or deny whether it has a relationship to the classified NSA program," the company said.

BellSouth said on Monday that "based on our review to date, we have confirmed no such contract exists and we have not provided bulk customer calling records to the NSA." A BellSouth spokesman was not immediately available for further comment.

AT&T has been more circumspect, saying it has an obligation to assist law enforcement and other government agencies but has refused to comment specifically on national security matters.

A company spokesman on Tuesday declined to comment about whether it provided the NSA access.

Electronic Privacy Information Center Executive Director Marc Rotenberg said the statements by government officials and phone carriers were "legal hair splitting."

"There's a tremendous amount of parsing going on," Rotenberg said.

Earlier on Tuesday, BellSouth and AT&T were added to a $200 billion lawsuit against Verizon which accuses the three large telephone carriers of violating privacy rights by turning over customer phone records for use in the NSA program.

The lawsuit, filed on behalf of 26 plaintiffs in 18 states, seeks damages for the estimated 200 million customers of all three companies.

"We're outraged at the actions of the NSA, the administration and the phone companies," Bruce Afran, a public interest lawyer from New Jersey, said at a news conference. He added that he wanted the companies to understand the massive financial exposure they had on this issue.

USA Today said it has read the statements by Verizon and BellSouth and would investigate the story further.

"We're confident in our coverage of the phone database story," said USA Today spokesman Steven Anderson. "We will look closely into the issues raised by BellSouth's and Verizon's statements."

President Bush last year confirmed that the NSA was eavesdropping without warrants on the international phone calls and e-mails of U.S. citizens while in the pursuit of al Qaeda.

After the USA Today report, Bush defended U.S. intelligence programs, arguing that the administration is obliged to "connect dots" to protect Americans after the September 11, 2001 attacks, but he has refused to confirm or deny the report.

"What I have told the American people is, we'll protect them against an al Qaeda attack and we'll do so within the law," Bush said. Late on Tuesday, the administration agreed to give let the full Senate and House of Representatives intelligence committees review the domestic spying program.

Commentary: