On a trip to Honduras a few years ago I visited one of the islands off its north coast with a friend and went to a section of it mostly with nothing but residences which looked far less visited by tourists and which had no live coral off the coast in that section of island unlike other parts of it. While in that area we saw what looked like a rocky protrusion a little off from a small beach, about 50 or so yards offshore, so my friend and I waded out to it and we were stunned to discover that it was a rather large exposed section of coral that had been completely fossilized. It was pitted in parts, reminding me a bit of the surface of the moon, but we clearly saw amazing varieties of coral and their fossilized contours and patterns in the "rock".
But more puzzling is that it protruded at its base a good 1-2ft above sea level on average (though erosion made the edges gradually slope down to the water) and up to probably between 5 to 7ft above sea level in some other areas where the coral [or mass it was on] protruded), which made the highest sections clearly higher than the beach we had just waded from. That seemed to indicate that the ocean level may have been quite a bit higher when it was still alive and parts of the island may have been more submerged at some point in the past if I had to guess.
Ignoring for a moment my imprecise measurements and notes about its exposure relative to sea-level, how long would it take any portion of alive and healthy coral to fossilize once exposed directly to the sun outside of/above water at its quickest, turning rock-grey and becoming firm, even if the fossilization process is not completed to its utmost extent? Can it happen in a few thousand years, or does it happen only at a significantly slower rate than that? Has any such process of fossilization actually been observed (as proceeding through its stages) at any point throughout recorded human history, and what would intermediate stages look like in terms of color, firmness, etc.?
I am not an earth scientist so you'll have to go easy on the explanation here.
Edit: I have now uploaded some photos to Flickr of the particular coral I saw. The "mini island" (I'll call it) was quite alien-looking and bizarre in places, also overgrown with some plants on the main mass, but you can, for example, see the close up I took of one fossilized bit of brain coral that was firmly set in the rock.
I also found a similar photo on Flicker taken by someone else taken from San Salvador (Bahamas) at what is identified as the Cockburn Town Fossil Reef, and the photo has an interesting scientific essay with citations in the image description.