Not having query hints isn't the "SQL at fault" - it's very much the optimizer, or you wouldn't need to override it with said hint. I've seen it where one index hit an arbitrary number of rows and then the query flipped to joining on another, non-indexed column, increasing the time to run massively - that sort of 3m to 3 hours magnitude. Had to throw on a hint but that's only because the optimizer decided it knew better.
And that's why I listed a bunch of other options as well - simplifying code is probably the best one, but there will always be gaps in their heuristics.
In my experience, you have one of three scenarios:
You know ahead of time exactly the problem you are going to solve and so probably shouldnt choose SQL from a performance perspective.
Your problem size changes and you get to pick a simple system that you understand well and has predictable performance but might be slower than other options.
Or a complex system that's less well understood, and generally has great performance and productivity up to a tipping point, where the abstraction has leaked too much.
In your case - your query sounds exactly like those heuristics worked up to a point, and then finally failed. Is that the optimizers "fault"? It's mostly a trade off between the time spent making the plan and the time spent getting your data back - and again, sometimes those tradeoffs are wrong too.
A slightly more charitable view of this situation is that an optimization which was previously triggering to make the query fast suddenly no longer applied.
I think that might be too optimistic - it went from a table with thousands of records to hundreds of millions of records. If I were to speak technically the oracle optimizer "did a derp".
So... stale statistics? I.e. the optimizer making the query plan assuming that the table has thousands of records (because that's what it had earlier) and now it has hundreds of millions of records? A sudden order of magnitude change in table sizes isn't normal operation, for most DB platforms that requires running some "everything's different now, please recalculate statistics" command to maintain proper functioning.