Saria and Navi have been the two most likely candidates for the "lost friend" mostly since no one else can really fit the description. Or Link would not wonder around in the Lost Woods looking for them, he would be looking elsewhere. Anyone else is either not going to be anywhere near the lost woods, Link already knows where they are (like Zelda or Ruto) or he would not be close enough to them to look for them.
Saria might be the one he is looking for, she is called Link's closest friend a few times in the story, but it is unknown when she left for the forest temple in the story, and when Link went back in time the troubles that caused the Kokiri Forest to be dangerous leading to Saria leaving might have been avoided.
"Oh, you're leaving... I knew... that you would leave the forest... someday, Link... Because you are different from me and my friends.... But that's OK, because we'll be friends forever... won't we? I want you to have this Ocarina... Please take good care of it. When you play my Ocarina, I hope you will think of me and come back to the forest to visit." — Saria
That meanie, Mido, made me cut the grass at Saria's house. Mido told Saria he would do it so she would like him, but I'm the one doing all the work! You and Saria are close friends, so will you help me cut the grass? I'll let you keep anything that you find while cutting it." — Kokiri
Saria did wonder out to the sacred forest meadow early in the game, since this is on the other side of the Lost Woods it could be possible that she somehow got lost wondering to it. The argument against it is, she had been wondering to the sacred forest meadow for so long she should know her way through the Lost Woods by that point. Also this could be after the Deku Tree had died but before the sprout had grown so there was no guardian deity protecting the forest and Kokiri could become lost in the forest.
"If you're looking for Saria, she's in the Lost Woods, as usual. Don't tell me you don't know where that is! The entrance is up on the cliff overlooking the village! I know you'll get lost! Don't worry, you'll just end up back at the entrance! Harumph!" — Mido
Also the real nature of a Sage is not known, it is also unknown if they went back to being normal individuals after Link went back in time at the end. Saria could have simply disappeared from the Kokiri Forest and became the same of the forest regardless of Link's changing history. It was said that she cannot come back after she awoke as a sage.
"Oh...I see... Saria won't ever come back... But...I...I made a promise to Saria... If Link came back, I would be sure to tell him that Saria had been waiting for him... Because Saria...really... liked... Hey, you. If you see him somewhere, please let him know... And also... I'm sorry for being mean to him. Tell him that, too." — Mido
This disappearance might have confused Link as well who went out to look for her beyond the lost woods in the sacred forest meadow or the forest temple.
Navi might make more sense as the lost friend since we actually see her leave at the end of OoT. Although she was not accompanying Link for very long to be the invaluable friend, they had only known each other a short time during the course of Link's adventure. And Navi was only assigned to Link for the purpose of helping him on his quest. While Link was happy to finally resemble the other Kokiri.
"A journey in search of a beloved and invaluable friend... A friend with whom he parted ways when he finally fulfilled his heroic destiny and took his place among legends..."
This does sound much more like Navi than Saria since they did part ways after he fulfilled his destiny. Since Link did return to the Kokiri Forest after the adventure he would appear out of place again without a fairy. And then might decide to go out into the forest to look for her again, not understanding why she left.
Another thing is, Link went through all those troubles in Termina, helped everyone living there, stopped Majora, and rescued the giants, but never actually did find that friend he was looking for at the beginning of the story. Whoever they are, they are still missing somewhere in the lost woods. This is less of a concern if it is Navi since she was capable of living in the forest before the was called by the Deku Tree to guide Link and could simply return without trouble.
