From reading about Cays on Wikipedia it seems they are formed from coral reefs covered with sand or gravel. There are however some cays scattered around the world which are hundreds of feet off of sea level at high tide. How did these cays form, or are they mis-classified islands?
its the same way atolls form, sea level changes and tectonic plates move while the corals keep growing up as the land sinks. Any spot high enough for coral to survive can slowly grow in this way. they can end up hundreds of meters above the sea floor by the slow gradual process of growing coral.
I find a simple animation makes it easier to follow.
Cays are just trapped sand in the coral reef, the sand can come from the erosion of nearby islands, volcanic, or even erosion of the coral itself. This is why most cays occur near other land masses or in volcanically active areas.
Just as land can sink it can also rise, pushing those deposits high above the waterline, note these cays are very rare. Also note the parts far above the water are dead ancient corals not living ones, although there may be leaving coral around the base. there are ancient fossil corals in the Himalayas after all.