Possible causes for 7-segment LED flicker
Flicker is a result of too slow refresh.  You need to refresh each segment at a few 100 Hz minimum.  However, there are some tricks that can reduce apparent flicker while not actually doing faster refresh.  The naive approach is to refresh the digits in order.  But, if you alternate them a bit, the whole number will appear to flicker less.  For example, do digits 1, 3, and 5, then come back and do digits 2, 4, and 6.

Without knowing the processor and seeing the source code, it's impossible to say whether the vendor is trying to string you along or the mess really needs to be re-written.  Keep in mind that 99% of firmware engineers write horrible firmware.  There could be hard coded constant all over the place that make assumptions about the clock frequency, the LED refresh rate, etc.  With well written firmware, increasing the refresh rate assuming the processor has the necessary cycles already should be easy.  With badly written firmware, it could be a lot more trouble than to ditch the mess and write it right.

How come the original designer didn't address the flicker?  Perhaps the firmware is so badly architected that simply increasing it wasn't possible?  If the flicker is that obvious, then why was the product ever created the way it is?  That alone makes it likely the original designer made a mess.  If he could have easily fixed it, he probably would have.

The really funny thing is now you're doing it again.  You are going overseas because you want to keep costs down.  Good design costs real money, but bad design costs much more.  Even though you have been bitten by that, you have still not apparently learned it.  With good design in the first place you wouldn't be in this position, and even if you were, it should be easy to change.  There is no excuse for changing stored audio not being a simple operation.

How do you know if it's a bad idea or not to change the microcontroller and the circuit if you don't know what either are?  Buying engineering strictly on price is the most expensive way to go.

Added in response to comments:

I don't remember where I heard about refreshing digits non-sequentially, but I have tried it and found it to help.  I think it works for the same reason interlaced TV appeared to flicker at the field rate instead of the frame rate.  For NTSC, the whole picture was redrawn at 30 Hz, but the apparent flicker was 60 Hz because of the interlacing refresh.  You're not going to get 2:1 like that by interlacing digits, but it does help.

No, 60 Hz is not fast enough, not even close.  60 Hz is about where most people don't see flicker anymore for a square wave.  Someone staring directly at a LED driven 50% of the time at 60 Hz may not see the flicker, but that's not the only way people perceive it.  Unless you only have two digits, the LEDs will be on brighter for a smaller fraction of the time, which makes the flicker more apparent.  The center of your retina is the slowest in responding.  You will notice flicker more at the periphery of your vision.  However the real objectionable part is when you move your eyes.  Flicker is easily apparent at 60 Hz.  You can't make the flicker invisible due to this phenomena, so the problem is to make it less annoying.  60 Hz is still quite annoying for most people.  As I said, you want a few 100 Hz at least.  If you have to pick a number, I'd start by trying to achieve at least 500 Hz.

As for getting good engineering, that's a whole topic on its own.  There is nothing inherently wrong with going overseas.  Competent people live in various places.  The issue is first to recognize that bad design will cost a lot more than hiring a top engineer to do it right in the first place.  Second, you have to realize that finding and vetting engineering talent takes some work.  You're going to spend 1000s of $, probably 10s of 1000s of $.  Treat it like other purchase decisions of that magnitude.  Ask around, interview, get references and actually follow up on them.

As long as you're serious and the job is real, I'd say you have the right to expect around 2 hours of initial consultation before any committment is made.  Keep in mind that goes both ways.  Part of this time is for you to evaluate the engineer, but of course the engineer is evaluating you too.  They are trying to decide whether this job fits in line with what they want to be doing, whether you are going to be a pain in the butt customer, etc.  Either way, there should be plenty of time to get into the requirements and talk about initial impressions of what path the engineer will persue towards the solution.  This should tell you a lot about how they think, how much they just implement whatever you told them versus drilling down and trying to get at the real problem and making sure that is solved, suggesting alternate solutions, etc.

None of this says the engineer can't be oversees, but it does make logistics and good evaluation difficult.  If you have a couple of strong recommendations from people you trust, then that helps a lot.  If you're logic is only that Bob in Boston wants $130/hour and is estimating 4 weeks while Naresh in Bangalore wants $35/hour and can do it in 2 weeks, you're headed for serious trouble.