Well given the lack of enthusiasm I'll just give the answer... I hope this thread isn't gonna die though :( .
First there were four, and in many directions, (Original clues on paper -steps)
Second were four more, but only one way or the other. (Safe combinations)
Third they couldn't be found. (Lost Number)
So the 'They' is actually talking about numbers. The second riddle:
First there were 123, then there were 12, referred to Lost Number.
Fourth there was something else, that made others half. (This talks about Odin)
What are they, and who came fifth?
The 'who' then is Vincent.
I kept the numbers theme going throughout the riddle as it seemed to fit, and to make it a bit harder perhaps. Guess it was too hard :P .