Queries may produce different execution plans after the first run because of cardinality feedback. In 12c this feature was renamed statistics feedback.
The optimizer uses information about the actual and expected number of rows from the first run, and uses that information to improve the second execution plan. In my experience this is usually a good feature. But all optimizer features can backfire occasionally.
There are at least two ways to tell if cardinality feedback is used. There will be a note in the explain plan:
Note
-----
- cardinality feedback used for this statement
Also the statement will show up in this query:
select * from v$sql_shared_cursor where use_feedback_stats = 'Y';
You may want to check both. When I tried to create an example the query had use_feedback_stats = 'Y'
but did not have the Note in the explain plan.