“Not all those who wander are lost.”

[davem]

Child Difficult one. I suppose Elves & mortals have a different relationship to the world - Elves belong in it & men don't - 'restlessness' is part & parcel of the 'gift' of Eru. So whatever Men achieve they soon become dissatisfied & begin immediately seeking something else. For Elves the Sea is the road home to the West, for Men it seems to have a more 'metaphorical' role. It doesn't lead them to a place of rest.

Therefore he willed that the hearts of Men should seek beyond the world and should find no rest therein; but they should have a virtue to shape their life, amid the powers and chances of the world, beyond the Music of the Ainur, which is as fate to all things else;

Men are wanderers in M-e & perhaps the Sea to them is the way to mysteries, to the unknown, rather than to a specific place. Elves seek the Sea as a road to a specific place, to Men it is a road to the unknown. It may even be that the fact that they cannot come to Valinor gives a greater symbolic significance to it as far as they are concerned - it may not lead to Valinor, but it could lead anywhere. Men would become restless even in Valinor. For Men (within the circles of the World at least) are driven to seek what they are doomed never to find.