SA295 went down off Mauritius in 1987 in waters up to 5,000m deep. There was a catastrophic fire on board resulting in severe break-up of the wreckage. Still, they managed to find the cockpit voice recorder. I suspect in this day and age they'll have no problem finding the recorders.