What do the Connection Properties look like in ArcCatalog when you create the SDE connection (Please provide a screenshot)?
Can you revert back to an 11g Oracle Client?
I believe I was testing an Oracle 12c Client and I had issues making the connection to Oracle SDE, so I stayed with Oracle 11g Client. My org also has now migrated to the Instant Oracle 11g client and so far it has been successful.
Do you have access to Pro to see if your Oracle 12c Client connections work better in that environment? You would need the 64-bit Oracle Client though.