big picture - Does the presence of cocycle conditions indicate the existence of an underlying cohomology theory?

I had lots of thoughts on that kind of question, and feel uneasy to speak as my answer can range from a tautology, through systematic and positive, but somewhat ignorant toward not-well understood cases, to mere impressions and (seeming?) "counterexample" oriented answer. The basic question is what you mean by a cocycle. Usually one talks on expressions of some higher categorical coherence, or about some notion of homotopy behind it. In such cases the answer is normally yes: the equivalent or homotopic cocycles will form cohomology classes and this can be in all understood cases done naturally and systematically. Higher nonabelian cohomology can be done for all $n$, as now many frameworks know (Brown, Jardine, Toen, Street...) and cohomology boils down to take homotopy classes into certain suspension of the coefficient object. For one recent framework we can advertise our own work (pdf).

I slightly believe anyway that some algebraic cases can be outside of the current homotopy categorical framework and I discussed that much on the n-category cafe, nforum and elsewhere. Namely model categories treat on equal footing homology and cohomology, while the minimal conditions on a setup to be able to do cohomology of homology is less than both simultaneously (cf. work of Rosenberg on "right exact structures" on a category, pdf).

Finally, we can imagine more complicated category-like structures where one can do much of the usual combinatorics but can not properly do the equivalence classes when needed for cohomology. There is one example which is maybe repairable, due Shahn Majid, namely he has a notion of bialgebra cocycles for a noncommutative and noncocommutative bialgebra. Now in special cocommutative or commutative cases like Lie algebras and/or abelian coefficients he recovers some known cohomology theories like Chevalley-Eilenberg cohomology for Lie algebras. In low dimensional cases he also gets some interesting nonabelian cocycles of much usage like Drinfel'd 2-twist and Drinfel'd 3-associator which are used in the study of monoidal categories, CFT, knot theory and quantum groups. In this example the differential and cocycles are defined for every $n$ but 17 years after the discovery, there is still no known way to define well the cohomology classes, for dimension 3 or more, for general bialgebra, despite the special cases and despite the cocycles and the differential. See the nlab page bialgebra cocycle for the basics (and the references therein).