To continue this, there is the quite interesting passage at MN 106:
“Ānanda, take a mendicant who practices like this:‘It might not be, and it might not be mine. It will not be, and it will not be mine. I am giving up what exists, what has come to be.’ In this way they gain equanimity. They approve, welcome, and keep clinging to that equanimity. Their consciousness relies on that and grasps it. A mendicant with grasping does not become extinguished.”
“But sir, what is that mendicant grasping?”
“The dimension of neither perception nor non-perception.”
This is admittedly the edited version of the statement (from ‘I’ to ‘it’) attributed to the annihilationists, but if someone is grasping the state resulting from the contemplation it’s functionally identical. The dimension of neither perception nor non-perception is, of course, that which the Buddha said Uddaka Rāmaputta was teaching.
Perhaps when the Buddha realized “this practice actually only leads to rebirth in the realm of neither-perception-nor-non-perception,” (in his autobiographical account of leaving his former teachers), he was realizing that with these subtle practices there was not a full cessation of suffering; he realized that there was actually an extremely subtle basis of consciousness remaining in the mind, and therefore left his teachers.
(This also answers some questions about his insights into rebirth before being awakened or inquiring on his own; had this been the basis of his goal, it would be a perfectly reasonable—albeit extremely profound—realization before attaining the threee knowledges).
This line of thought would also make sense in terms of first leaving Alara Kalama and moving on to Uddaka Rāmaputta. The dimension of nothingness is a less subtle station of consciousness than neither-perception-nor-non-perception, and thus it is easier to have the realization that this state is not the true cessation of perception/personal consciousness (perhaps called ‘saññā’ in certain Upanisadic passages). At some point, the Buddha may have realized that whatever practices they were doing resulting in this state—believed to lead to the cessation of all suffering and personal consciousness —were actually still leaving a trace of perception behind, namely, the perception of nothingness. This caused him to realize consciousness was still personal, grasped, and being stationed, hence not an escape from a form of existence. He then went to Uddaka Rāmaputta who taught an even more subtle state, not even a ‘station’ but a base of consciousness (c.f. DN 15), and not necessarily a state of perception (by definition). Therefore, it was only after further practice that the bodhisatta realized that Uddaka’s teaching too was just a form of rebirth / stationing of one’s personal consciousness.
Eventually of course the Buddha, reflecting on dependent arising, realized that all consciousness was itself dependently arisen and it was the grasping that kept this stationing going, held in place by the very notions of a concept of self (attavadupadana, etc.). Therefore he realized the cessation of suffering is not annihilation, but relinquishing the notion of being annihilation and trying to do practices to station the mind into a state of self-annihilation; relinquishment was the true path. Therefore he used the jhānas, especially the fourth which is based in upekkhā, to see clearly into the structure of experience and the conditioning of consciousness, able to relinquish all ignorance and grasping, and the āsavā (such as bhavāsavā—the current of mind trying to go to or remove oneself from forms of existence).
This is extremely relevant for Bhante @sujato’s post on DN 9 and perhaps nevasaññānāsaññā, and the cessation of perception.
https://discourse.suttacentral.net/t/the-po-hapadasutta-is-a-direct-response-to-yajnavalkya
Excuse the clunky writing! Lots of ideas coming together and converging here though.
Mettā 
