Find the former brewer and stick his lazy butt in the kettle with your assortment of cleaning apparatus and chemicals. Keep locked in kettle until the kettle is perfectly clean and individual has learned the first lesson of brewing beer; cleaning and polishing kettles!
But seriously, even a good soak with hot PBW for several days will loosen up the baked on mess and allow most of it to be scraped off with a good SS scraper, restaurant scrubber, and good application of elbow grease. Afterwards, any mineral film deposits can be scrubbed away with a low-fuming foaming acid cleaner applied at high strength and a green scrubby pad. I use 5-Star StarSan or Ecolab Lime Away mixed with a little Quaternary Amonia (Quantum from 5-star) to give it some foamy surfacting properties. Keep rinsed off after cleaning a section to prevent any possible corrosion. Make sure to do an additional mild caustic CIP to get rid of the Quat and then repassivate the Stainless with a Nitric Acid wash.
If the kettle was that bad, I am sure the fermenters and bright tanks are equally soiled. If the beer stone or lime scale is really bad, I have used a strong dilution of Muriatic Acid and hot water about 1/2 gallon per bbl and run CIP for about 2 hours. Rinse with cold water, climb in with your foaming acid, green scrubby, SS restaurant scrub pad, SS scraper, and foaming acid cleaner and get to work. Remember, stone likes to build up on inside of pipes as well. That is going to take even more work to clean out. Get lots of brushes.
Good luck.
Todd G. Hicks
BeerDenizen Brewing Services