The ODD EVEN DELTA problem is #P-hard, even on 3-regular bipartite planar graphs.
Let $\mathcal{C}$ be the set of vertex covers of a general graph $G$. Then, assuming $G$ has no isolated vertices, the following equation holds (refer to the above article for the proof):
$$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$$
Counting vertex covers is #P-complete even on 3-regular bipartite planar graphs, and it can be done with a linear number of calls to an ODD EVEN DELTA oracle.