My companies Ops Manual and other winter ops documents used to explicitly state a "Clean Aircraft policy". In other words, no contamination allowed.
Lately however this has gradually been diluted. The old mantra no longer appears in the books, and most operators manuals (jet types) allow up to 1/8th inch of 'hoar frost' on the fuselage as acceptable. They even suggest that if you can read the logos on the fuselage through the ice then you have around 1/8th inch contamination...and can go.
Personally I don't feel comfortable with this and I insist on a clean aircraft. Among the reasons...if you have contamination on the top of the fuselage you probably have it on top of the wing too!
It only takes a few minutes more to spray the fuselage, but I still get funny looks from engineers and even some F/O's who are quick to remind me what th book allows as acceptable!
The difficulty is that many other skippers accept this level of contamination...including training Captains. Makes it a lonely path to tread at times, but still less lonely than the graveyard.