Why can't I reverse a hash to a possible input? I'm going to provide “proof” why a hash function can be reversed, and I hope you can tell my why I'm wrong

So, a hash function can be implemented as a series of logic gates. All logic gates can be implemented using only NOT and OR gates. (I'm fairly sure about both of these, but please correct me if I'm wrong.)

Therefore, a hash function can be implemented as a series of NOT and OR gates.

A NOT gate can be easily reversed by going through another NOT gate.

An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output.

Therefore, I should be able to construct a possible input given an output from a set of logic gates, including from a hash function.

What have I gotten wrong here?
It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction of gates is a function, rather than depending on some internal state. And the number of gates is manageable (perhaps in the order of $n=10^{5\pm1}$ OR gates for the SHA familly and single-block message).

This does give a constructive way to find an input corresponding to a given output, as outlined in the question: try every possible inputs for a gate with an output that's a given output, or has been hypothesized in an earlier step. For NOT, there's only one possible input (the complement of the output). If the output of OR is 0, its inputs are 00. If the output of OR is 1, there are 3 possibilities for its inputs: 01, 10, 11. When a new hypothesis conflicts with an earlier hypothesis (which occurs since inputs of different gates can be connected to the same output), eliminate the new hypothesis. If all new hypothesis for a gate's input(s) are eliminated, eliminate the old hypothesis. When all the circuit is covered, and if there's a possible input, any hypothesis not eliminated gives a possible message input.

That works. But critically: new hypothesis are dependent on earlier ones, thus when we meet an OR gate with a 1 output, it multiplies by 3 our number of hypothesis to keep track of (in a breadth-first approach) or explore later in case of failure (in a depth-first approach). If we examine the maximum number of hypothesis to be examined as a function of the number $n$ of OR gates, it grows as $\mathcal O(c^n)$ for some constant $c$ that can be significantly above 1. Using that a XOR can be built with 3 OR gates (and some NOTs), we have an argument that $c\ge\sqrt[3]2\approx1.26$ for some large portion of some possible circuits (adding a XOR gate on an unknown input transforms it into 2 unknown inputs).

Thus the argument in the question proves that a hash can be reversed with enough effort, but it gives no lower bound for the corresponding effort; and the best bound we know to derive is exponential w.r.t. the gate complexity. It turns out that for hash constructions used in cryptography (e.g. SHA-1 with 160-bit output and 176-bit input), the cost of this method is much higher that trying all possible hash inputs (e.g. $2^{176}$).