[Ibrîniðilpathânezel]

It may not exactly fit with the Melian story, but it does give a pointer, I think. Not all of the Noldor were unfriendly with the Elves, and I suspect that if Feanor had other gems of his making, he might well have taken them with him when he left Valinor (especially given his anger at the Valar, and his unwillingness to have others touch his creations without his leave). Even if it didn't come from Feanor, he wasn't the only jewel-smith in Middle-earth. Celebrimbor was the greatest jewel-smith of Eregion, and by one version of the story in UT, created the version of the Elessar that came down to Aragorn through Galadriel. Since the smiths of Eregion were at one time friendly with Durin's folk, it's entirely possible the Arkenstone was made by them and given to the Dwarves of Khazad-dum as a token of the peace between them. Thorin was a direct descendant of Durin's line, so such a gift might well have become a treasured heirloom of his house, despite the animosity that eventually grew between the Elves and Dwarves.

Then again, this could be an example of what happens when things change in rewriting and revising. New things are substituted, but not all of the loose ends are removed. Could happen.