(FORTUNE Magazine) – ON PAPER, THE CLEANUP OF Hurricane Katrina should be a business bonanza and public relations coup all wrapped up in one tidy package for Louisiana's Shaw Group. The $3.1 billion construction and environmental-services company (No. 557 on the FORTUNE 1,000) specializes in the sort of work needed to rebuild after disasters. It has been tackling hurricane projects since Andrew in 1992 and was pre-approved for federal contracts. Shaw sprang into action after the storm hit, putting electricity into hospitals and giving away free food and water to victims from its Baton Rouge headquarters. Then, a few days later, it was awarded $200 million in "no-bid" reconstruction money from the federal government. And this once nearly invisible company went from zero to Halliburton in 60 seconds.

Rather than feasting on the good publicity that might be due a hometown company helping out in a crisis, Shaw has now become a target for journalists suggesting it was awarded the contracts because of its ties to the Bush administration. The alleged smoking gun: a consulting agreement with Joe Allbaugh, former director of FEMA. Allbaugh denies lobbying for contracts. And three Shaw board members contacted by FORTUNE bristle at accusations of favoritism. "We've got no affiliation with these fools in Washington, the Bush administration," says director Albert McAlister. "We certainly don't pull political strings to get our work."

On Katrina at least, Shaw deserves the benefit of the doubt. One of its contracts is to pump water out of New Orleans--a job that can't wait for a months-long bidding process. Even watchdog Beth Daley of the Project on Government Oversight agrees no-bid deals are "ideal for an emergency situation."

Ironically, even as Shaw was being grilled for connections to D.C. Republicans, it was also being flayed for its deeper links to Louisiana Democrats. Shaw CEO Jim Bernhard, who has pondered a U.S. Senate run, played a key role in Governor Kathleen Blanco's 2003 election. Last December questions were raised when Blanco convinced Union Tank Car to build a facility in Louisiana--and Shaw got a key contract. Then came news that the governor and her husband had hitched rides on Shaw's plane. Bernhard raised even more eyebrows by taking on the chairmanship of the state's Democratic Party. As scrutiny of Katrina contracts intensified in mid-September, Bernhard resigned as party chairman, citing a need to focus on the company.

Until the political flaps, Shaw was known for its 16-year leap from startup piping firm to diversified FORTUNE 500 corporation. Acquiring Stone & Webster, a builder of power plants, and IT Group, which handles environmental and infrastructure work, allowed it to take on contracts around the globe, including one to inspect and remove munitions in Iraq.

Despite some recent troubles--Shaw posted a loss in 2004 and announced an informal SEC accounting inquiry--the company is returning to profitability and even feeling acquisitive. Shaw is considering a bid for Westinghouse, the nuclear unit and vestige of the former industrial giant. It says something that for Shaw these days, nuclear power qualifies as politically uncontroversial. -- Nicholas Varchaver