We have no way to be sure, but probably not.
No source attests to the existence of the Immortals except for Herodotus. Opinions are split on his reliability, but it is believed that Herodotus did not personally speak Persian.
In Paligaro's view, Herodotus or his informant confused here the word anusya ("follower", "adherent") with the word "anausa ("immortal").
Dandamaev, Muhammad A., and Vladimir G. Lukonin. The Culture and Social Institutions of Ancient Iran. CambrSidge University Press, 2004.
We have no reason to disbelieve that the Persian king was guarded by a unit of companions. Macedon had the Companion Cavalry, for instance. It also stands to reason that they were an elite force. Maintaining a unit at constant strength is hardly a frightening feat in and of itself, unless state propaganda hyped it up as "immortality".
So if no unit called "Immortals" actually existed, why should the Greeks have known to fear its "immortal status"?
Furthermore, the account given by Herodotus hardly suggests fear on the part of the Greeks. There is no trace of it in the passage cited in the question. In fact, Herodotus seemed much more concerned with the Immortals' appearances than either their reputation or fighting prowess - mentioning only in passing that they were the best of the Persian army.
From The Histories, 7.83.3,
The Persians showed the richest adornment of all, and they were the best men in the army. Their equipment was such as I have said; beyond this they stood out by the abundance of gold that they had. They also brought carriages bearing concubines and many well-equipped servants; camels and beasts of burden carried food for them, apart from the rest of the army.
Herodotus goes on to list the Persian cavalry and nomadic units in the Persian army. The impression is that he was describing an order of battle, not putting the Immortals on a pedestal as a unit to be feared.