Does Oracle randomly switch execution plans to check if there is a better solution?
Whenever the optimizer looks at a query to produce a plan the relevant statistics are examined and it will compare the cost of various plans and pick the cheapest.
It doesn't look at all possible plans as it can 'shortcut' some options.

An execution plan will be produced whenever a hard parse occurs and this only happens when the query to be executed does not already exist in the shared pool.

So . . . the execution plan might change over time as your database may change over time, e.g. that small history table you had last year now has 20million rows rather than 10,000 so the optimiser decides to use an index instead of the full scan.

I've come across many 'tipping points' for the optimizer in the past but they are hard to predict at a granular level because we don't know exactly what algorithms the optimizer uses.

Oracle wont however change its execution plan 'just to see' if it already has a plan for the query.

Maybe the person you spoke to was referring to the new adaptive plans in Oracle 12c but that still doesn't mean Oracle will sometimes try a different plan. Look here for info on adaptive plans https://blogs.oracle.com/optimizer/entry/what_s_new_in_12c