Well, considering
THIS you may want to search near Ibiza.
No, but really I think that the disappearence of the palantiri was again a proof of the growing gap between the world of Men and the world of Elves and Dwarves and Hobbits.
Same thing probably happened to the Elessar and to other "magical" substances like mithril and ithildin. Simply forgotten as time passed.