What is a markedness constraint in Optimality Theory?

First thing to remember is that in OT, constraints do not allow, they forbid. Second thing to remember is that markedness constraints are about all representations, not just featuress. Third thing to remember is that all constraint, not just markedness, are claimed to be universal. Fourth thing to remember is that while it is a prevalent trend in OT to attributute constraints (all contraints) to perception and production factors, that is not a defining feature of OT, it is a theory-internal hypothesis. Fifth, there aren't separate principles of phonetics that are the basis of constraints. However, in those sub-theories where constraints can be learned, phonetic factors can result in learning of a particular constraint – this is (apparently) the Hayes line on phonetics-phonology, and is analogous to the Hale & Reiss line on substance dependence in rule based phonology.

In general, OT predicts indeed takes as its basic axiom (therefore it is not even a prediction) that all effects are the result of constraint ordering. No output can ever be free of constraint violations, because the constraint set penalizes every structure, so it is always and not just almost always necessary to violate some constraint, for every form in every language (not just "a grammar", writ large). Forms never correspond to constraint, they satisfy or violate constraints.

You didn't characterize markedness constraints at all, you characterized constraints in general, with some reference to phonetic considerations. I think the simplest solution is to look at what things correspondence ("faithfulness") constraints refer to, and what the other constraints refer to. Correspondence constraints state relations between "corresponding" elements of representations (not just one representation). The relationship may be between input and output, or between candidate and some output form, or between two candidate, and can also be computed on different subparts of a (candidate) string, e.g. Base-reduplicant correspondence. They are mediated by correspondence indices, which is how you get "the corresponding segment in the input". There are various hypothesized relations that may exist in the correspondence set, which are variations on the themes "exists", "(immediately) precedes", "is the same". With one exception, markedness constraint just look at the properties of the candidate – the exception, which is not widely accepted in modern OT, is the two-level constraint, which is a markedness constraint that adds the codicile "if X is present in the input". Dep and Ident constraints have rendered that machinery irrelevant.