It sounds like much of what they found was ballast, which may have been heavier material like rocks/metal, and they identified it based on it being an anomaly c

It sounds like much of what they found was ballast, which may have been heavier material like rocks/metal, and they identified it based on it being an anomaly compared to the surrounding seabed and journal entries made by Columbus. As for your question, I wish I knew, though I recall from an Anthropology course I took that the older wooden artifacts tend to be found in peat bogs over a thousand years after being deposited. If I understand correctly, the condition isn't great, but the peat bogs themselves prevent oxygen from entering the environment and decrease decay rates of organic material. A quick search shows that peat bogs can exist under the sea so the conditions you describe might exist even under warm water.