There is one simple solution you might try for this particular query:
create a composite index on (C536870923, C3).
The index should be better than each of the existing indexes, and should be picked by the optimizer in almost all cases.
Also, you might consider disabling bind variable peeking. Disabling, in and of itself, would not help directly, but it might bring stability.