Dick Cheney was angry.

He was answering questions at a meeting of foreign policy experts in Washington last week. Then he got a query about the U.S. decision to de-list North Korea from the terrorism blacklist.

“It was a fascinating, little bit scary moment because the vice president … just went stone silent” says the questioner, Steve Clemons of the New America Foundation. Cheney gave a non-answer and exited the room.

That moment sums up the tragic contradictions of the Bush administration’s foreign policy. In the never-ending battles between its pragmatists and uberhawks, the North Korea deal marked a huge defeat of the Cheneyites and a victory for Condoleezza Rice.

But this was a deal that could, and should, have been done at the beginning of Bush’s first term. As John Bolton, our former United Nations ambassador and a harsh critic of the deal rightly said, this deal is “the same thing that the State Department was prepared to do six years ago. If we are going to cut this deal now, it’s amazing we didn’t cut it back then.”

It was not done then because Cheney’s views were then ascendant. In the meantime, North Korea became a dangerous nuclear power. Now, with their legacies in mind, Rice finally convinced the president they should try to change North Korean behavior through painstaking diplomacy, rather than pursue the chimera of regime change.

Bush’s change of heart has infuriated Republican superhawks. “This is a sad, sad day,” said Bolton. “I think we’ve been taken to the cleaners.”

Wrong.

Yes, the deal’s imperfections are apparent. Pyongyang has turned over 19,000 pages of documents of its plutonium production program for making nuclear weapons, and has blown up the cooling tower at its main nuclear reactor. It has yet to reveal, however, the details of a secret uranium enrichment program. (Most experts don’t believe that program got far.)

Also missing are accounts of its sales of nuclear technology to other problematic nations, like Iran and Syria. Israel recently blew up a Syrian facility that supposedly was a nuclear reactor being built secretly with North Korean help.

The North Koreans, the most infuriating of negotiators, were six months late in turning over the documents. Verification will be difficult but crucial. Much needs to be confirmed in next 45 days, during which Congress can review the deal.

And, yes, the superhawks are correct to call the regime of Kim Jong Il despicable. It has starved its own people and sentenced untold thousands to death camps. One issue that slowed the deal was North Korea’s failure to come clean with Japan over the fate of scores of Japanese who were kidnapped from Japanese coastal areas. The abductees were forced to train North Korean spies. Some have been returned to Japan, but the fate of others is still unknown.

President Bush said he would work with Japan to resolve this issue, and he should do so. He did not, however, mention the equally tragic case of U.S. permanent resident and Christian missionary Kim Dong-shik, who was abducted by North Korean agents in northeast China in 2000 while helping desperate North Korean refugees flee their country. If Kim is still alive, he presumably is suffering inside a North Korean prison. This case, too, needs resolving.

The bottom line, however, is not whether the deal is imperfect; it is whether a deal makes visible progress toward ending North Korea’s nuclear program. “We believe our policy could verifiably get the (North Korean) regime out of the plutonium-making business,” Rice wrote in the Wall Street Journal. That is a big deal.

The Cheneyites have never admitted their path has led only to failure. The White House debunked and backed off a 1994 U.S.-North Korean deal that had shut down Pyongyang’s plutonium program. The result: North Korea unsealed the reactor, enriched six to 10 bombs worth of plutonium, and tested a weapon. Nor did the Cheney approach do anything to improve Pyongyang’s terrible human-rights record.

For years, Bush permitted multilateral talks but no direct U.S. contacts with North Korea – a charter member of the “axis of evil.” Only when Rice finally let U.S. negotiator Christopher Hill engage directly with his North Korean counterparts in 2007 did talks finally move forward. Cheney was reportedly furious.

Future progress will be slow and incremental. North Korea may backslide. But removal from the terrorism list provides only minimum economic benefits. Other sanctions won’t be dropped before Pyongyang lives up to its commitments. “What if North Korea cheats?” Rice asks rhetorically. “The answer is simple. We will reimpose … sanctions.”

Her message sounds so logical, so pragmatic. Negotiate, assess progress, look for incremental change rather than the transformation of nations. What’s unclear about the new White House pragmatism is whether the president has connected the dots on stopping dangerous nuclear programs, dots that connect Libya to North Korea to Iran.

Direct talks led to the end of Libya’s nuclear program, and hold the best chance to curb North Korea’s. But the wait of seven years will make it much harder to reach that goal with Pyongyang, and exponentially harder to reach similar results with Tehran.

The burden will fall on the next president. Hopefully, he will learn from this one’s mistakes.