The Day Zero recruiters' (which included some marquee names in global banking) loss was ICICI Bank's gain. And the relationship that started in the summer of 1980 lasted 29 years.
She and her husband, Sanjay, were batchmates at IIM-A, and until last year, the joke among their friends was that they were the only couple from that class to have stuck to their first jobs. Sanjay is still with the Tata Group.
Though she moved on to head Axis Bank, India's third-largest private sector bank, eight months ago, Sharma just can't stop talking in glowing terms about her mentor KV Kamath (now ICICI Bank chairman), who gave her assignments she never thought she could pull off.
Even though the last six months at ICICI Bank were tough due to speculation over her exit, Sharma says the most important thing for her at that time was to ensure that her relationship with Kamath wasn't fractured.
"We had very transparent conversations - he understood my needs and I understood where he was coming from," Sharma, 50, says.
But it must have been quite disappointing when the MD and CEO's job finally went to Chanda Kochhar, we ask. Sharma just rolls her eyes and asks if people are still interested in the so-called "Chanda-Shikha story".
"We have healthy regard for each other as professionals. In any case, my stint at ICICI Bank, though beautiful, is a closed chapter in my life," Sharma says.
Wasn't she annoyed with the constant questioning on the "Chanda-Shikha" story? "No. I understand that it's part of a journalist's job and he/she is paid for it. I only wish customers were as understanding when they got marketing calls from my bank staff," she says with a smile.
We are at the Taj President's Thai Pavilion restaurant and are led to what can best be described as a table stuck into a hole in the floor. Wriggling into our seats involved some acrobatics but Sharma is sporting enough and manages to move in.
We persist with knowing her "closed chapter" and ask about her experience about moving from ICICI Bank, which is (or at least used to be) a byword for aggression, to an organisation with a more deliberate approach to business.
The answer, as usual, is measured: "The advantage of being a CEO is that you build your own culture. In any case, a CEO's job is a lonely one and I'm used to it," she replies, referring to the eight-odd years she spent at the helm of ICICI Prudential Life Insurance, her previous assignment.
The waiter appears with three tome-sized menus, but Sharma decides to cut to the chase and go with the chef's recommendations of prawn soup to start with, followed by Thai fish curry and stir-fried vegetables paired with noodles.
Her brush with succession issues, however, doesn't end quite as soon. While the first ended with her quitting ICICI Bank, the second led to her predecessor at Axis leaving in a huff. Question her on this and the answer is: "Life is a mirror. If you go on expecting negativity, you will find negativity."
Sensing our disappointment with the rather philosophical answer, Sharma is quick enough to say, "Axis Bank staff might have initially asked, 'Why is this person here,' and from their perspective, it is a perfectly legitimate question. But if you start worrying about that, you are just setting yourself up for failure."
The arrival of the soup offers a break from the discussion on knotty successions and angry exits.
She obviously didn't worry about those "legitimate questions" while bringing in the changes she has made at Axis Bank. She is confident that the bank will continue to beat the industry growth rate and sustain the margins and return ratios.
Apart from a slew of senior management reshuffles in corporate banking, she has formed a dedicated infrastructure group. On the retail banking front, where she admits Axis is under-represented, she has recast the business along customer lines rather than product lines.
In the process, there have been some high-profile hires and exits, but Sharma says that's fine as long as the relationships remain professional.
The food is standard five-star fare, but Sharma seems to be enjoying it partly because she just loves sea-food. She is proud of the fact that she belongs to that generation of female executives, many of whom have moved into the boardrooms, hitherto a male bastion.
"My professor recommended ICICI partly because it had a reputation for being gender-neutral. When I joined, Lalita Gupte (who retired as joint MD of ICICI Bank in 2006) was already at a senior position."
Sharma agrees that a lot of talented women do leave after becoming mothers, but says if one can engage them and pull them back, they can cope.
"The first two-three years after becoming a mother are the toughest," she says, recollecting how her heart would sink at the thought of leaving her child at home.
"Even if you are doing really well at work, but feel you are not a good mother, the guilt can shatter you," she says. But Sharma was lucky to have a "terrific" support system at home - a reason why she has been able to maintain a 12-hour work routine and give her best to the job.
An economics graduate from Lady Shriram College (LSR) in Delhi, IIM-A was the only part of her early life that was planned. In fact, Physics was her first choice for an undergraduate course but she settled for economics because the former was not offered by LSR.
But she has no regrets as economics gave her enough opportunity to prove her formidable skills in maths - a subject very close to her heart.
The lunch is over and Sharma settles for a quick cup of tea. There is, however, a fallout of being a CEO: She can't visit her son who is studying computer science in the US, often enough.
However, her husband visits him once every semester. "In any case, my son says having two parents over at the same time is too much to handle," she chuckles.
While we clamber out of the "hole", Sharma says despite her busy schedule, she never works on Sundays - a day reserved for reading Mills & Boon novels. And she just loves Hindi films which, she says, are great stress busters.
"Sanjay and I first see the ratings given by newspapers and anything above three is okay with us," she says - a reason why she has watched Paa, 3 Idiots and even Chance Pe Dance, all in quick succession.
Her only regret is that she has had to take a break from sessions on Hindustani classical music with her teenage daughter, for the last eight months. "Singing can help you de-stress; it, in fact, reduced my migraine problems. I just hope to get back to it soon," Sharma says.
As we wait for her silver grey Honda Accord to pull up, Sharma talks about how 2009 would look like a picnic compared to 2010 when things would be much more challenging for banks in terms of managing economic recovery in a volatile market. Going by that, the singing sessions would have to wait a while.