The campaign for of the 2008 presidential election is echoing another political battle between the two heavyweights the 2000 Senate race. But voters never had a chance to choose between them because Giuliani had to drop out of the Senate race for health reasons.
In March 2000, Giuliani was the mayor of New York City who held a slight lead in the polls over then-first lady Clinton as they geared up for their history-making Senate race showdown. It was a political drama custom-made for the New York tabloids: the tough-talking, crime-fighting former federal prosecutor versus the most famous woman in the world with a husband in the Oval Office.
She was, he said, the interloper from Arkansas via Washington and "a leader of the ultra-left wing Democrats" who would use the Senate seat "as a springboard" to run for president.
He, she countered, perhaps lacked the proper temperament to serve in the Senate because "the mayor always gets angry about things."
But the race that was supposed to rival the 2000 presidential fight between Vice President Al Gore and Texas Gov. George W. Bush never came off.
Giuliani was diagnosed with prostate cancer in April and, after the breakup of his second marriage became public knowledge in May, he quit the race. She coasted to victory over a little-known congressman from Long Island, Rick Lazio.
Fast forward to 2007. The race that might have been could wind up being The Race.
Clinton leads national polls for the Democratic nomination for president. Giuliani leads for the Republican nomination. A Time magazine national poll out last week had Giuliani leading Clinton, 47 percent to 43 percent.
"Salivation time for tabloid reporters," said Hank Sheinkopf, a Democratic strategist who worked on President Bill Clinton's 1996 re-election campaign, but is not involved with the current Clinton White House run.
"Neither one of them are what you would call gentle campaigners," added Maurice Carroll, director of the Quinnipiac University Polling Institute.
So far, the two campaigns have largely ignored each other except for the occasional swipe from the ex-mayor, who is selling himself nationally as the Republican candidate best equipped to beat her.
At the annual Conservative Political Action Conference in Washington early this month, Giuliani told the crowd that when he became mayor, he thought he could reform the city's school system.
"OK, I made mistakes. I'm going to admit them and apologize for them," he said with an impish smile and a strategic pause. The laughter grew as it dawned on the crowd that he was taking a poke at Clinton's refusal to say her 2002 vote to authorize the Iraq war was a mistake.
"It's been my home turf longer than Hillary's," Giuliani said at the St. Patrick's Day parade in New York City when asked about the prospect of running in a general election against Clinton in her home state. True, but polls show her well ahead in heavily Democratic New York.
While the two camps refused to publicly discuss how a 2008 showdown might play out, citing their concentration on the race at hand, supporters were less hesitant.
"It would be a wonderful matchup," said Guy Molinari, a former congressman and former Staten Island borough president long allied with Giuliani. "The politician in me says that's what we all hope happens.
"I'm very, very confident Rudy wins that," said Molinari, recently named a co-chairman of Giuliani's New York campaign. "Rudy's good in the pits. He's no shrinking violet. She's not either."
"My experience with Hillary Clinton in New York was that the more people met and got to know her, the better they liked her, while the opposite was true for Rudy," said Judith Hope, former state Democratic chairwoman.
In fact, before he became "America's Mayor" in the wake of the Sept. 11, 2001, terrorist attacks, the often combative Giuliani had an up-and-down relationship with the gritty city he governed.
In April 2000, just before learning he had cancer, Giuliani's approval rating among city voters dropped to 37 percent, a new low in the Quinnipiac poll. In the wake of the fatal March shooting of an unarmed man by police, Giuliani drew criticism for his release of Patrick Dorismond's juvenile record, suggestions the victim had been responsible for his own death and refusing to offer condolences to his family.
Clinton has her own problem with numbers.
"The thing about Hillary that is attractive to me is that her negatives (in the polls) are off the charts," Molinari said.
Sheinkopf cautioned that a 2008 contest between the two won't look like the one that eventually fizzled in 2000.
"They are very different people, in very different places and in very different times since 9/11 in New York," he said. "She's a senator with a six-year record to defend. He's America's hero."
And, Sheinkopf noted: "They both have warts."
Both, for instance, have rocky marital histories - he's been married three times and had one particularly bitter divorce. Clinton endured her husband's Monica Lewinsky affair.
While Carroll said a Clinton-Giuliani contest "would be a lot of fun, and who the hell knows who would win," he said he doesn't hold out much hope it will come off.
"It doesn't show up in the numbers right now, but I have a gut feeling that it just isn't going to happen," he said.