By definition, one who is immortal is unchanging and ageless, and therefore age would not have effect on the physical ability to procreate.
It could be argued that the mortals that share lineage with the immortal would not have had their bodies develop a different set of rules out of the blue when dealing with Elvin procreation aspects. If there is a physical reason for a loss in ability, it is due to the wolf blood.
Of course, do we know if Go-Backs are immortal after the wolf was clensed from them by Willowgreen? It seems that they should be, but we never see it. They keep dieing on us fighting the Trolls.
From a metaphysical/philosophical standpoint, however, the older an Elf is (mortal or immortal), the less chances there are to meet new people, and the less chances for "spontainious Recognition" (like Cutter and Leetah). "Non-spontainious Recognition", such as Cutter and Skywise, seem to occur when two individuals have shared everything with themselves already, and spent a long period of time together already. Some couples have even shared soul names without recognition, only to recognise down the road. Again, the longer you are alive, the less chance there is to meet new people, and among those you know already you've already befriended or found adversity with at some point, so you would have already recogised. From this perspective, it's not necessarily AGE that affects ability to recognise, but rather TIME.
One last point: If at some point a mortal (or injured immortal) did come to a point in their lives that their bodies could not bear children, this would not necessarily mean that they could not recognise. Cutter and Skywise could not procreate and still recongised, it follows that the infertil would also be able to recognise, and perhaps do... they might just keep it to themselves.
Thought of one more thing to note while posting elsewhere: if there were "too old" limitations for all Elves, Timmain would have passed that point LONG LONG ago, as the origional High Ones are countlessly older than the time they spent on Abode. Further, it seems that procreation is also an ability that can be "forgotten" and "remembered" among Elves, as the Cone Heads hadn't had children that we know of for a unknown but long period of time.
Also, I'm not sure of this, but it seems that there was a line somewhere that "Recognition" was described at one point to be a mechanism of design to enforce procreation at some point after the crash on Abode. By this reasoning, Timmain would not be bound by it, and may have been the instigator of it, perhaps as a solution to the High-One's infertility?