While investigating flaky pov-recovery test behaviour, I found that it sometimes fails because data is still Unavailable on the relay chain.
Example Test
Node Logs

We are starting recovery as soon as we see a candidate pending availability. Since availability is not guaranteed, it can happen that the candidate is not yet available on the relay chain. We should have a backup mechanism that retries failed recovery requests.