I don't think we've got any non-Greek evidence that the Immortal corps even existed.
Given that mixed formations of spearmen and archers seem to have had a long history in Mesopotamia, I'd be tempted to assume Persian infantry was sparabarah style from very early on. It seems more likely they adopted the style before rather than after the conquest of Babylonia, because conquerors are rarely in much hurry to copy the system they'd just defeated.
(That said, there's a lot of time between the conquest of Babylonia and Herodotus' battle-accounts, so maybe hurry wasn't needed.)
I'm disinclined to put much store in the story about Cyaxares' reform, because mixed formations of spearmen, archers, and cavalry would be decidedly odd. More likely we're seeing a folk memory of Cyaxares as a culture hero bringing order to society in general. And while it's prima facie plausible the early Persians were more influenced by their Median overlords than by their Mesopotamian neighbours, if we assume they used separate units of spearmen and archers under Median influence, we must then also assume a switch (?back) to mixed formations, which isn't terribly parsimonious.