The far-right Shiv Sena party made international headlines in 1995 when it forced the change, but many residents continue to use the old colonial name out of politics or habit.
Mumbai is a beautiful city but Lahore is where I was born and bred: Fawad Khan
With the Bombay High Court and Indian Institute of Technology Bombay just two of several institutions still using its English appellation, foreign tourists could be forgiven for feeling confused.
"When Bombay became Mumbai everything else should have followed and I don't know why it's taking so long," Arvind Sawant, a Shiv Sena lawmaker for south Mumbai, told AFP.
Shiv Sena is strongly pro-Marathi, the dominant language and ethnic group in the state of Maharashtra, of which Mumbai is the capital.
Karachi bleeds while Mumbai ready to flourish
The party renamed the western Indian city after the goddess Mumbadevi, the protector of fisherman who were the area's original inhabitants, shortly after being elected to run the state government.
Marathi speakers had always called the city "Mumbai", and the move was popular among that community, whereas "Bombay" was an anglicised take on the Portuguese colonial name "Bom Bahia", or "good bay".
Mumbai's switch was one of a number of Indian city name changes in recent years, notably Chennai, which used to be Madras, and Calcutta, now known as Kolkata.
After India's central government officially approved Mumbai's renaming, the city's civic body, called the Bombay Municipal Corporation, became the Brihanmumbai Municipal Corporation in early 1996.
A friendship that transcends borders
But some other state institutions remained unchanged and Shiv Sena, now a junior partner in the state government, has unfinished business as far as the renaming programme goes.
"All of the government institutions have to be changed," said Sawant, who wants the Bharatiya Janata Party-led central Indian government to start by agreeing to Shiv Sena's demand to rename Mumbai's top court.
Shiv Sena lost power in 1999 and the renaming of the historic courthouse, which was established in 1862 under British rule, dropped off the agenda.
"The Bombay High Court should be the Mumbai High Court. I've raised the issue in parliament and the government has to follow through with it. We are demanding that they change it now," the MP told AFP.
Refused entry: Pakistani family spends night on a Mumbai footpath
India's Justice Minister DV Sadananda Gowda has reportedly agreed to put the proposal to the cabinet before tabling it in parliament, where it is likely to be passed.
Sawant also has public university IIT Bombay in his sights but admits that persuading private establishments, such as the Royal Bombay Yacht Club and Bombay Gymkhana, to dispense with part of their heritage will be more difficult.
"We cannot force them to change their name but we expect them to and they should do it now," he said.
The director of IIT Bombay and the CEO of the Bombay Gymkhana both declined to comment when contacted by AFP.
No space, no issue: Mumbai temple allows Muslims to offer Eid prayers
"If they want they can change, but nobody can compel them to," Indian National Congress MP Husain Dalwai said, adding that Shiv Sena liked to trumpet "these emotional types of issues".
"Bombay" and "Mumbai" are used interchangeably, for example The Times Group publishes the "Mumbai Mirror" newspaper and also the "Bombay Times".
"Many people change what they call the city depending on what language they are talking in," said Naresh Fernandes, author of "City Adrift: A Short Biography of Bombay".
The names "reflect the multi-lingual character of the city", he added.
While the two names tend to live happily side by side, earlier this year musician Mihir Joshi fell foul of India's Central Board of Film Certification when it objected to his use of Bombay and bleeped the offending lyric out of his video.
Mumbai attacks: India, US urge Pakistan to bring perpetrators to justice
"Mumbaikars" point out that Mumbai was the city's original name while some "Bombayites" feel the name change was too closely associated with the Bombay riots of December 1992 and January 1993.
Shiv Sena leaders were accused of inciting anti-Muslim violence that left more than 1,000 people dead. It swept to power in state elections shortly afterwards on the back of its pro-Marathi stance.
"It's Bombay for me and always will be," Fernandes told AFP.
"I think because it followed so closely after the riots that to many of us it was really a name change soaked in blood," added the writer, who covered the renaming as a journalist.
But two decades on and with the city's youngsters having grown up knowing their home only as Mumbai, Bombay's time could soon be up.
"When my generation passes on, maybe Mumbai won't stick in the craw in the same way," Fernandes said.
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ