I think that the "mottling" is coming from JPG (or other format) artifacting. That's what happens when you save the file multiple times. One thing that I do is to only work on copied files, and keep the originals untouched. That way I can start with a clean file if I need to enlarge or do some crazy photoshop work.
I'm a fan of programs like Geniune Fractals and QImage. They apply noise reduction as part of the interpolation process, and that can lead to loss of detail and artifacting. Try it with just the size palate in Photoshop. I don't even use the 'Bicubic Smoother', just the regular 'Bicubic' setting, but you can experiment.
Lastly, lose the loup. The closest you should be looking at the screen is with Photoshop at 100%, and a good rule of thumb for prints is close enough to see the entire print without turning your head. You don't see people with magnifing glasses looking at the Mona Lisa.
David Buzzard