Is it true that no company has previously been indicted for failing to pay taxes on benefits given to employees?
Probably true, and even if not, it's very uncommon.
After an hours long search with many different keywords, I could not find any examples of a company being indicted for failing to pay taxes on benefits given to employees. I could find examples of employees being indicted (and, futhermore, pleading guilty) for failing to pay taxes on such benefits. The New York Times has written that such a move would be "highly unusual" according to several lawyers (who also couldn't come up with any examples). (If anyone knows differently, please correct me!)
In the 1990s, the IRS investigated NBA referees for not paying taxes on money they pocketed as compensation for air travel.
Another NBA referee was indicted by a federal grand jury on charges he downgraded first-class airline tickets purchased by the league and pocketed the difference without telling the Internal Revenue Service. ... [Joe Crawford's] attorney said he would admit his responsibility in failing to report the fringe benefit income. (CBS News)
The 45-year-old referee was charged with tax evasion and obstructing federal tax laws. The indictment says Mauer received "substantial taxable income" from 1989 through 1994 but failed to declare it. ... At least 11 other NBA officials pleaded guilty earlier. (Associated Press via Deseret News)
An ESPN article wrote that 45 NBA officials "have been lynched" in connection with these cases:
Mauer is one of the 45 NBA officials who have been lynched -- fairly or unfairly is up for debate -- by the Internal Revenue Service for an airline ticket scam that netted them additional income. ... Worse, while the other 43 referees who chose to plea bargain and wanted their jobs back got them back, Mauer possibly may not be reinstated by the NBA, depending on what the outcome of his sentencing hearing -- yet to be scheduled -- is.
With the benefit of hindsight, Mauer was indeed reinstated as most of his fellow colleagues were. Surprisingly for me, news stories are sparse, though there's a brief Wikipedia page on this.
From reading articles on these and similar enforcement actions, I have the impression that it's usually only individuals, and not companies, who are indicted. (e.g. take a look at IRS Criminal Investigation Press Releases or the list of Office of Labor-Management Standards Criminal and Civil Enforcement Actions dating back to 2001; note that these are all individuals who are sentenced/charged/indicted, even when something illegal they are getting indicted for benefits the company they work for, as in this case.)
Given 1) the large number of NBA officials charged, 2) these officials pled guilty and got their NBA jobs back, and 3) that the NBA itself wasn't charged, I would cite the NBA referee case as another example that indicting an organization itself is uncommon, even if problems within an organization are pervasive and (potentially) reflect more on the organization rather than on individuals.
On the Trump Organization case specifically, the New York Times wrote:
Several lawyers who specialize in tax rules have told The New York Times that it would be highly unusual to indict a company just for failing to pay taxes on fringe benefits. None of them could cite any recent example, noting that many companies provide their employees with benefits like company cars.
(Since this is not clear in the question, the Trump Organization has not actually been indicted yet.
Update on July 1, 2021: The Trump Organization has since been indicted.)
I also asked this question on Law.SE. The only answerer could not come up with an example of a company being indicted for failing to pay taxes on fringe benefits, though they could come up with an example of an individual being indicted for such a thing. Based on searches of links provided in the answer on Law.SE, I was still unable to come up with an example. You can read the answer for other legal perspectives if you are interested.
What about the other answer?
@DenisS's answer lists 3 examples of "owners of businesses", i.e. individuals and not the businesses themselves, being indicted and going to prison. In addition to @Nate Eldredge's comment that @DenisS's answers are on avoiding payroll tax and not avoiding taxes on benefits, these examples relate to individuals but not businesses getting indicted.