The first clue was that the two fundamental theories of physics so far were incompatible. The maths just didn't work out. It wasn't practical to perform a direct experiment to find out what happened in a situation where the two theories disagreed (it would have required a tame black hole, or a particle accelerator the size of the galaxy) but it was what should have tipped us off that something was very very wrong with our understanding of the way things worked, fundamentally.
The second clue came when efforts to build a useful quantum computer failed. All the theories predicted it should work, but the outputs were random - it was as if the wavefunctions decohered above a certain number of qubits - once the system reached a critical level of complexity it seemed to just fall apart. But nobody could figure out what the source of the interference was. Physicists were excited at first - the discovery seemed to open up avenues to new physics. But whatever experiments were conceived, the results just didn't seem to make sense - almost as if the very complexity that caused these effects was obscuring what was really going on.
The breakthrough came, of all places, in the attempts to simulate the human brain. Despite the protests of those who claimed it was cruel or unethical to create a simulation of human brain, it didn't take long for people to start trying, once computers because powerful enough to simulate the activities of 100 billion neurons and 600 trillion synapses.
However, none of these experiments created anything that ever seemed to be conscious in the same way that humans are. The sim-brains had the same kinds of rhythms and unconscious functions as a real brain, they could respond to stimuli and even learn, but not matter what stimuli were applied or what initial connections were made, these brains never displayed any hint of sentience, consciousness, creativity or free will.
Eventually all other factors were ruled out and it was determined that some kind of quantum gravity effects must be influencing the human brain - effects that we did not know how to simulate.
And then finally it was figured out. Quantum gravity means that time itself is curved and intertwined with space on very small scales much as it is on very large scales. Events in the future can influence events in their own past to some extent, and this happens in the human brain. Consciousness can only manifest in the presence of these closed timelike curves, solving fantastically complicated systems of equations instantaneously by feeding the answer back in time. Essentially, collections of neurons were accessing some kind of consciousness oracle that our deterministic computers did not have access to.
The next problem, then, was to build something that manipulated quantum causality the same way that the human brain did. Nature achieved this so it only made sense to suppose that we could do. And we succeeded, but what we found made us realize that things were even more mysterious than we had imagined.
To be continued...