If you can't see the grain on the print, the lens is out of focus; seriously, telling someone that they're "used to digital sharpening", without even contemplating the possibility that the lens may have lost focus is poor customer service.
Get yourself in with a lab who has an operator/operators who understand printing, and you can't go wrong. They'll be able to adjust printing to your negs, know when something is suddenly "off" (and reprint accordingly) and keep the lab running well. A lab that has operators who have no idea (or just plain don't care), won't give you the results your looking for, rather excuses without taking the time to consider you may be right in your observations.
I ran a semi-pro lab for almost 15 years - lenses can (and do) drop focus over time. If they're doing their checks correctly (every morning & monthly), they'd see right away that the focus is out, if not (or the operator is blind!!) no way they're going to admit and correct. I used to test each type of film monthly, with the supplied "Kodak Shirley" negs, that showed colour drift and focus capabilities.
Only once during that time did I need to have a lens re-calibrated, it had "drifted", slightly soft. Called the Kodak technician and he was there the following morning, sending another spare lens to tide us over in the meantime, which arrived within the hour.
It's not rocket science, but sometimes, people find it all too hard and just let it slide: "Near enough is good enough." Not words that were used in my lab, the team took pride in what they were doing and always strived to get the best out of the negs they received, regardless of it being pros or amateurs who dropped off their film. In our eyes, everyone was a professional - every shot was priceless to the customer, we just helped make it into a reality.