Nadal, playing his first competitive match since losing to fellow Spaniard David Ferrer in the U.S. Open fourth round on September 4, struggled to find his rhythm in the opening games, but eventually settled on the ultra-fast hard court.
The Spaniard got the measure of a fading Baghdatis in the second set, making the crucial break in the ninth game to claim victory at the scene of his triumph in 2005.
"I made some mistakes at the start and my serve was average, but I'm not unhappy," Nadal told a news conference.
"The match against Murray is going to be very tough and I'm sure if he hadn't injured his wrist in Hamburg earlier this year we would be talking of a player who would be in the top two, three, five or six in the world."
Third seed Novak Djokovic had to shake off a determined challenge from unseeded Fernando Verdasco to win 6-7 6-3 6-3.
The 20-year-old, who lies behind Nadal and Roger Federer in the rankings, will face Juan Carlos Ferrero in the last 16 after the Spaniard got the better of compatriot Carlos Moya 7-6 6-4 in a duel between former world number ones.
Djokovic did his best to garner support from the partisan crowd at the Madrid Arena by donning a Real Madrid shirt as he walked on court to face Verdasco.
But the Serb, who won in Vienna at the weekend and is already assured of a place in the season-ending Masters Cup, found himself on the back foot against the young Spaniard and lost the first set on a tiebreak.
He fought back to take the second 6-3 and gained the edge with a break in the eighth game of the third to clinch victory in just over two and a half hours.
SEEDS TUMBLE
Eight seeds including Masters Cup hopefuls Tommy Robredo, James Blake, David Ferrer, Ivan Ljubicic and Richard Gasquet tumbled out of the tournament on Wednesday, denting their chances of making the prestige event in Shanghai.
Robredo fell victim to Argentine Juan Martin del Potro who defeated the eighth seed 6-7 6-4 6-3 in a marathon late match that did not finish until well after 1am local time.
Eariler, wildcard Feliciano Lopez delivered a blow to seventh seed Ferrer's hopes of qualifying with an unexpected 7-6 7-5 win on centre court, while Mikhail Youzhny was brushed aside by Germany's Nicolas Kiefer.
Sixth seed Blake lost to Mario Ancic 6-3 6-4 and Czech Thomas Berdych exited at the hands of Argentine David Nalbandian who came from a set down to claim a 4-6 6-4 7-6 win over the ninth seed.
Gasquet lost to Paul-Henri Mathieu in straight sets in an all-French second round contest and Ljubicic, who was beaten by Nadal in the 2005 Madrid final, was edged out by Austria's Stefan Koubek 6-3 6-7 7-5.
Last year's losing finalist Fernando Gonzalez, seeded fifth, had to dig deep to record a 7-6 7-5 win over the combative Nicolas Almagro.
Argentine Guillermo Canas also had to battle hard to snatch a 6-3 3-6 7-5 win over compatriot Agustin Calleri and earn a third-round match against Federer.
