The Phoenix would be truly dead.
Reading through J.K. Rowling's statements on the veil, one sentence that stuck out to me was this:
It's the divide between life and death. I tried to do a nod to that in the Tale of Three Brothers - she was separate from them as though through a veil. You can't go back if you pass through that veil, you cannot come back. Or you can't come back in any form that will make either person happy anyway.
Vault 27 entry number two
It seems to me that, at least from this quote, there would be no escape for any living (or non-living) entity, including a phoenix; retrieving the ashes from within the Veil would be like retrieving a human's body.
One important thing to note is that although not directly stated, the fact that phoenixes live “to an immense age” would seem to mean that they do eventually die.
The phoenix lives to an immense age as it can regenerate, bursting into flames when its body begins to fail and rising again from the ashes as a chick.
Fantastic Beasts and Where to Find Them