The most fascinating part of my trip to Iran in late May was how much Iranian officials wanted to talk about holding talks with the United States.

Soon after I left Tehran, Secretary of State Condoleezza Rice reversed nearly three decades of U.S. policy on Iran and announced U.S. willingness to talk directly with Iranians. Such meetings would be part of broader, European-led negotiations on Iran’s nuclear program.

Given the gulf between the two sides, this tête-À-tête may never happen. But the Iranians’ murky political system and negotiating style shouldn’t obscure the mutual benefits of such a dialogue. If the Iranian regime is serious, talks could help stabilize the Middle East.

Skeptics will point out that Iranian President Mahmoud Ahmadinejad has called for Israel to be “wiped off the map.” He has also made clear he believes Iran’s interests lie with Russia and China rather than with the West.

But Ahmadinejad is not the man in charge of Iranian policy decisions of this magnitude, I was told repeatedly by Iranian officials and analysts. Elected leaders are subordinate to senior clerics. Foreign policy is in the hands of Iran’s supreme leader, Ayatollah Ali Khamenei, who has endorsed talks with the United States.

“Agreement to negotiate with the U.S. comes from the leadership,” I was told by Foad Sadeghi, director of Baztab (BusStop), one of Iran’s most widely read Web sites. Sadeghi is close to Mohsen Rezaee, former head of Iran’s powerful Revolutionary Guards and head of the Expediency Council, which screens all political candidates.

“If our presidents … had the power to make such a decision,” Sadeghi continued, “you can be sure that Mr. Hashemi (Rafsanjani) and Mr. (Mohammad) Khatami would have already negotiated with the United States.” He was referring to past overtures by these two former presidents, overtures the United States rejected – in part because of suspicions they didn’t have the support of Khamenei.

But even if Khamenei has endorsed a dialogue, can this regime be trusted? Iran supports Hamas and Hezbollah, which are on the U.S. terrorist list, refuses to recognize Israel, and is stirring the pot in Iraq. The Europeans, and even Russia and China, want Iran to satisfy concerns about whether its nuclear program is peaceful or is meant to produce nuclear weapons.

Yet officials working under Khamenei indicate many of these issues could be on the table if talks on nuclear issues were expanded. “The United States needs Iran’s help, not confrontation,” I was told by Mohammad Jaafari, deputy to Ali Larijani, Iran’s chief nuclear negotiator. “Iran is the one who can help in Iraq, Afghanistan, Syria and Lebanon. If the present administration doesn’t realize that, the next one will.”

Jaafari’s confident prediction stems from the fact that the Iraq war has strengthened Iran’s hand in the region. America ousted Iran’s two chief enemies, the Afghan Taliban and Saddam Hussein. Saddam’s fall produced a Shiite-led government in Iraq that depends on support from co-religionists in Iran.

However, the United States and Iran have common interests in stability in Iraq and Afghanistan (even though Iran has been meddling in Iraq to create problems for U.S. forces). Jaafari’s message was that Iranian-U.S. rapprochement could improve matters in Iraq. Indeed, he would have been the lead negotiator had U.S.-Iranian talks on Iraq not been postponed.

Jaafari’s larger message was that America needs Iran’s help in the entire Middle East. In other words, the United States should be conducting a broad strategic dialogue with Tehran, not just talks on Iraq or nuclear weapons.

Would Iran be willing to discuss its aid to terrorist groups, and an end to its inflammatory policy on Israel? Would it accept that Washington would continue to press human-rights issues? Unclear. Would it consider freezing its nuclear program? So far officials say, “No.”

What is clear is that Tehran wants U.S. recognition of its new role as Middle East power broker. “Ayatollah Khamenei’s diplomacy … is based on national interest,” Sadeghi told me. “If he feels that the U.S. will not give concessions to Iran, negotiations will never occur.” (This may explain Khamenei’s remarks that Iran does “not need” talks with America.)

“Ayatollah Khamenei will not sell Tehran’s visa to anyone cheaply,” Sadeghi said. “If the U.S. wants to solve its problem in the Middle East … it is better to think in terms of mutual concessions with Iran.”

If Iran is indeed open to “mutual” concessions, such a grand bargain is worth considering. Otherwise, any dialogue will fail.