It sounds terrible from your description. If the work shop has taken the bother to order a new set of decals it should in theory give a nice result. A good paint job is worth it if you can afford the money and you get the result you like, I understand you well; but like leonf mentions, it cost less to find a machine in reasonably good condition. Personally I accept a few signs of age and use, but I clean, polish and give it a few touch ups.
With a bit of luck; try to find the spots where the paint glues part stuck, you might be able to force the parts free, cut it with a racor blade or thin blade knife. Can you post a picture?