So the CMYK recipe calculated by photoshop is the best or there are other options?
Yes, you can work with any hungry printer with a commercial press who'll guarantee neutral CMYK grayscale with no color crossover errors and provide the instructions for you to aid in helping them reach YOUR goal. Have them sign an agreement indicating what your goals are and if they don't agree, go seek another hungry printer who will. It's not like commercial press technology is in its infancy.
These guys know how to get the job done as long as you pay them and from the list of printers available shown in Mark's linked PDF those and many others will want your business and bend over backwards to reach your goal of a CMYK neutral grayscale by any means necessary.
The "Process Color Manual" (corrected the name) result I posted above is sort of like a canary in the grayscale coal mine of printing "Standards" in that you can check the Photoshop numbers against the swatches to see how much variances you get from a random sampling off a commercial press that didn't come up with the swatches using an ICC profile.
Those swatches are pretty much like a "Raw" dump of CMYK color number combinations that present a neutral appearance comparing against a Photoshop ICC based recipe. The fact that one mid gray swatch located out of 24,000 from a Photoshop ICC profile number recipe would look neutral not knowing the variables (which you seem to be trying to compensate for unnecessarily) that generated it, shows "Standards" are pretty easy to attain by the industry that's been printing CMYK color over 50 years. You'ld think these guys would know how to produce a decent CMYK grayscale and they do, so you shouldn't be so concerned about it on the front end.
Just work with a printer who'll listen to your concerns and sign an agreement indicating what you want.