Hello again Bhante, hello others, 
Got some more time than yesterday when I replied very briefly. Long post, but don’t worry, I’ll bring it back to the topic!
That’s just a silly story, as if I’m just making things up out of thin air (or sucked it out of my thumb, as the Dutch say!) But I have actually thought about things for once! 
There’s many actual reasons why it would be more sensible, and would better fit the suttas as a whole, if the Buddha didn’t attain jhanas under his former teachers. Here they are, for those interested: (And it makes a good story too.)
All of us agree the Buddha rejected sensual pleasures when he went forth, like the three similes in MN36,85,100 also tell us. And later he rejected the pains of the self-mortification. Put aside his former teachers for a moment. Then here’s what seems to have happened next: He wondered, what was the alternative to such pleasure and pain? He realized it’s the pleasure of the jhāna that he once experienced when younger. He then realized he was afraid of it, but there’s no good reason to be. So while up to that point he had avoided the jhanas out of fear, he decided he should now pursue that pleasure. (Notice he doesn’t say anything about views.)
That would explain why later he said he discovered the middle way that avoids sense pleasures and self-mortification (and not the way that avoids wrong views). In DN29 Sāriputta even specifically says the avoidance of these two extreme is the four jhānas:
The Buddha doesn’t indulge in sensual pleasures, which are low, crude, ordinary, ignoble, and pointless. And he doesn’t indulge in self-mortification, which is painful, ignoble, and pointless. He gets the four absorptions—blissful meditations in the present life that belong to the higher mind—when he wants, without trouble or difficulty.
That’s strikingly similar to the Dhammacakkapavattana Sutta where the Buddha said he woke up to (or ‘discovered’ if you will) the eightfold path that avoids both these extremes—the path which of course finishes with the four jhānas.
To me, that seems to be the point: that, alongside the rest of the path, the Buddha found a new kind of happiness that he hadn’t really pursued before. That his former teachers just lacked right view to me is unconvincing. Even the whole stint of asceticism then seems to serve little purpose, narratively or otherwise.
Let’s summarize the path as sīla, samādhi and paññā. Sīla was essentially a new idea, being based on intention instead of Vedic rituals or Jain karmic particles. Of course the paññā was new (which, btw, shows his former teachers’ paññā wasn’t true paññā, so why would their samādhi be true samādhi?) So why wouldn’t the samādhi be a new discovery too? It doesn’t seem too unreasonable to assume.
And isn’t that’s exactly what he states when he said he realized the first jhāna was the path? He didn’t say, “back then I attained a jhana without having a wrong view.” He just states that he entered the first jhāna, and that he realized that he should no longer fear it. I prefer to take that statement at face value. Others can disagree, of course. One can read this jhana statement in light of his former teachers account. Or we can read the former teachers account in light of this statement. I wouldn’t want to pretend like any one of them is the only or obvious interpretation (or story), though. It clearly isn’t, given that many people have wondered about this before.
Then there are also quite a few suttas that effectively say samādhi leads directly to seeing things as they are (eg AN11.2), and that the seven enlightenment factors (which are centered around meditation, not view) similarly lead to awakening. And of course in the Dhammapada that jhāna and wisdom go together. He even said the seven enlightenment factors (i.e. meditation, essentially, since these starts with sati and end with equanimity) are the path. (SN47.21) Once he even said just samādhi is the path. (AN6.64) This all rhymes if jhāna was indeed central to his discovery.
Then, the deva Pañcalacaṇḍa said: “The Buddha who woke up to (or ‘discovered’ if you will) jhāna […] has found the opening amidst confinement,” where the opening is jhāna and the confinement the five sense pleasures. (SN2.7, AN9.42) In SN45.14 the Buddha said the eight factors of the path don’t arise without the appearance of a Tathagata. Could mean the path as a whole, but it can also be read as each factor, including samādhi. And in DN10, upon hearing the four jhānās explained by Ānanda, the Brahmin student Subha said: “Among renunciants and brahmins of other schools I do not see such a fulfilled noble set of samādhi.” The Ratana Sutta states: “The supreme Buddha extolled […] samādhi to which no equal can be found." We can take these all to mean he realized the importance of jhana in context of right view, though that’s never explicitly stated anywhere, or we take them to say he actually “found the opening” himself, as he seems to have done when he recollected the first jhāna.
Also, and I think very importantly, in a number of suttas it very much seems the Buddha started developing samādhi only in the period just before his enlightenment—which would make a whole lot of sense if he just realized jhana was the path and had avoided them earlier ot of fear. MN19, for example, presents his problems with thoughts while developing samādhi and follows it up directly with his enlightenment. MN128 mentions a whole list of obstacles, including noticeably fear, and it also leads straight to enlightenment. If indeed he was already proficient in the formless attainments, having attained them “very quickly” according to the former-teachers passage, I wouldn’t expect all these troubles to attain samādhi just before his enlightenment. Moreover, these texts (like also AN9.41 and MN4) never even even so much as hint at his former experience with the formless, let alone his former teachers. It seems very much like he was doing his own thing. He always says he understood (“it occurred to me”) that these things were obstacles, and that he realized how to overcome them. He wasn’t told by anyone. AN9.41 furthermore follows such stuggles to get the samādhi attainments with the cessation of perception and feeling, which further indicates this development didn’t happen under his former teachers.
Some more minor points:
As I briefly said before, some parallel versions of the noble search mention his former teachers only had three of the five faculties—faith, energy, and wisdom—leaving out mindfulness and samādhi. I got that from Ānalayo’s Comparative Studies of the Majjhima. The omission of samādhi wouldn’t make much sense if his teachers did attain the formless states, so we might be tempted reject these parallels straight away, like Ānalayo does. But the usual corruption of a text is when things get leveled. In this case it would have been easy for a reciter to accidentally expand the three faculties to the standard five, since they are used to reciting them as a group elsewhere. It is less likely they were taken out. So what if his teachers didn’t really have samādhi and all they had was basically just theories about it, or perhaps just some alternative meditation that wasn’t true samādhi?
We can add to that that in the Upanishads and other pre-Buddhist texts meditation and especially samādhi are basically non-existent, if there at all, as far as I can tell. As I said before, as far as my limited knowledge goes, the Brahmins usually thought mere conceptual knowledge was enough, which probably stems from the idea of the memorization of the Vedas being considered liberating in and of itself. Ramaputta called himself a knowledge-master (vedagū), which seems to refer to such scriptural knowledge too.((SN35.103))
So then, here’s what I think happened, and which is also the story I read: The Buddha rejected sensual pleasures when he went forth, rejected conceptual/scriptural knowledge and theory under his former teachers, and rejected asceticism after his austerities. Having rejected household life and the two major religions of the time (Brahminism and Jainism), he then formed his own path based on an earlier memory of jhāna. 
I’ve left out what could be said from a psychological point of view. First, that inside the jhānas and arūpas you can’t have a theory, whether right or wrong. The first jhānas the bodhisattva would have attained under his former teachers would have been the exact same state of mind as the first jhāna in his earlier days. There’s no difference even between the jhāna of an unenlightened person and an enlightened person. (Which explains why they are called the happiness of awakening and described with the exact same words for the Buddha as for anyone else.) So that makes it even more unexplainable why he recalled the jhāna he had before he met his teachers. He would have recalled the more recent ones.
And also, the jhanas are so similar and close to gaining insight (e.g. AN11.2, “It is natural that one who is concentrated knows and sees things as they really are.”) that I find it totally unbelievable the Buddha went all the way to the very end of the formless attainments and then still went so horribly wrong as to practice asceticism to the point of almost dying! That may be a nice story, sure, but I think incredibly, incredibly unlikely to have actually happened. Come on, neither-perception-nor-nonperception is just a hair’s breadth away from nibbāna. Absolutely no way the Buddha would have missed it. Especially since nibbāna can be seen from the first jhāna already. (AN9.34, MN52)
In fact, that the former teachers taught him all the way to the highest non-cessation states is so remarkably convenient for a good story to make the Buddha out to be a natural meditator, that it has to be exactly that: a story. So very “coincidental” the first teachers he met taught him exactly those two states…
Which brings me back to the topic: Some have argued the formless attainments are late parts of the path partly based on the Buddha’s account of his former teachers where he “rejected” them. But it’s more likely to have happened the other way round: His former teachers account may be what’s late. They could for example have taught something else which was either forgotten or got too obscure for the reciters to relate to, and these formless states were put in place later. Correct me if I’m wrong, but in the Pali Canon this former teachers story is just the one passage, repeated a handful of times in the Majjhima Nikāya. That makes it more likely this passage is unoriginal than the very many texts that incorporate the formless attainments in various ways. We all know the texts are far from perfect records (32 marks of a great man, anyone?) so in light of all I’ve said I don’t think it a ridiculous assumption to say something may be off about the teachers passage.
And the best thing about all this is… in the end it doesn’t matter at all! Because we got the path laid down for us regardless of how the Buddha got there. Which is why later I will respectfully read all of yours lovely replies, but probably not argue my ideas much further.