Greedy algorithm doesn't do that well in the worst case, even provided the odd cycle counting oracle.
Take large $n$, and consider complete bipartite $K_{n, n}$ with parts $V_0, V_1$ together with an additional disjoint triangle $T$, and connect all vertices of $T$ with two vertices $v, u \in V_0$ pairwise. Odd cycles in this graph consist of even paths in $K_{n, n}$ between $v$ and $u$ extended by an odd path in $T$ (either a single vertex or a Hamiltonian path), together with a single Hamiltonian cycle in $T$. One can see that:
- $v$ and $u$ are contained in all odd cycles except for one;
- vertices of $T$ and other vertices of $K_{n, n}$ are contained in fewer odd cycles.
A smallest OCT consists of two vertices of $T$, yet the greedy algorithm WLOG will first take $v$, and then will proceed to delete at least two other vertices (since the remaining graph contains $K_4$, namely, the union of $u$ and $T$).