The Department of Interior's Office of Inspector General report comes amid rising pressure from Congress and environmentalists to make sure taxpayers are getting their fair share of coal sales.
Critics of the leasing program seized on the Inspector General's findings and called for a temporary halt in sales until changes can be made.
In 2011 alone, companies with leases on federal lands produced 473 million tons of coal, and the report said undervaluing sales by even a penny per ton can result in millions of dollars in lost revenue.
But industry representatives noted that the losses were relatively small in the context of a program that brought in almost $4 billion in revenue during the last two years.
"It's a rounding error," National Mining Association spokesman Luke Popovich said of the government losses detailed in the report.
About 40 percent of U.S. coal is extracted from federal lands in 10 states, with money derived from leases and royalties equally split between federal and state governments.
The Powder River Basin of Wyoming and Montana accounts for the overwhelming majority of the public coal sales, and 90 percent involved just four industry giants: Arch Coal, Peabody Energy, Alpha Natural Resources and Cloud Peak Energy.
Most of that fuel was burned in U.S. power plants. But as domestic sales lag due to competition from cheap natural gas, increasing volumes of U.S. coal is being shipped overseas, a trend that the Inspector General's report suggested the government has failed to keep up with.
It also noted that 80 percent of the coal sales in the Powder River Basin over the past two decades received only one bid, a lack of competition also seen in other parts of the country. While that makes it harder to determine the fair market value of coal sold by the government, that task remains crucial, the Inspector General's Office concluded.
Beyond the lost revenues, the report pointed to shortcomings in Interior's coal mine inspection and enforcement offices that "could prevent BLM personnel from detecting noncompliance with laws, regulations and lease terms."
Concern over the federal coal leasing program has drawn increasing scrutiny from Congress, with lawmakers including Oregon Sen. Ron Wyden and Alaska Sen. Lisa Murkowski questioning whether companies are making profits at the public's expense.
Industry opponents went much further Tuesday, with Jeremy Nichols of WildEarth Guardians declaring the coal leasing program "broken."
"The coal industry is getting breaks beyond belief," Nichols said. "They should have to pay their fair share for a public resource, a public resource that incidentally is taking a tremendous toll on our environment."
Representatives of the Bureau of Land Management, the Interior Department branch that oversees government coal sales, said the agency concurs with most of the recommendations in the report. That includes a re-assessment of how export coal is valued, making the leasing program more efficient and improving its inspection program.
That work will be done by the end of 2014, the agency said.
"The BLM will continue to diligently work to improve the operation of the federal coal program," said agency spokeswoman Celia Boddington. She added that the agency "is committed to ensuring that the American people receive a fair return" on coal sold from public lands.