Ages of the Valinor and the Ice Ages.

[James the Just]

So Melkor almost wiped us out right from the beginning. No wonder no one could find us for some time.
Elves aren't exactly immortal. Some of the nobility age at only 1/144th the rate of humans. It depends on where they're living, Aman (America) or Middle-earth (Europe). Check (G)NoMe for more details.

Speaking of Gnomes why aren't their rings normally included?

Three Rings for the Elven-kings under the sky,
Five for the Gnome-princes over the sea,
Seven for the Dwarf-lords in their halls of stone,
Nine for Mortal Men, doomed to die,
One for the Dark Lord on his dark throne
In the Land of Mordor where the Shadows lie.
One Ring to rule them all, One Ring to find them,
One Ring to bring them all and in the darkness bind them.
In the Land of Mordor where the Shadows lie.