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 paths in $K_{n, n}$ between $v$ and $u$ extended by a two-vertex path in $T$, together with $O(1)$ odd cycles confined to $\{v, u\} \cup T$. One can see that:
- $v$ and $u$ are contained in all odd cycles except for $O(1)$;
- vertices of $T$ and other vertices of $K_{n, n}$ are contained in at most $2 / 3 + o(1)$ fraction of all 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$).