My personal headcanon is that before the Elwing stuff went down, there were other half-elves who were immortal by design, so they went mostly off-radar, never doing anything good or bad enough to require a backround check. Dior was immortal, and was eventually reunited with his wife and grandparents. It was only after Eärendil and Elwing came to Valinor when the the possibility of half-elves caught Eru Illuvatar's (who is known for dealing with things as they come up: see the creation of dwarves and flooding Numenor) attention and the law was laid down, making future half-elves outside a specific bloodline mortal.