Anyway, in the unlikely case that I'm right about how phoenixes work then this theory goes a long way towards explaining what they're for. Imagine that one or two Atlanteans develop a magical machine to scan, store and replicate people, but they keep the method to themselves because of it's obvious evil applications (for instance, infinite cloned slaves). At the same time, though, there are loads of very very GOOD applications you could put this technology to, saving lives and storing the scans of people who are on the verge of death so they can be replicated and healed when a cure has been invented. Solution: make the machine indestructible and imbue it with a sort of Absolute Morality Golem (i.e. - build a phoenix), so that it yearns always to save people and do good. Of course, there are situations in which this won't maximise utility, so you stipulate that the phoenix should always seek out a good, wise human to serve, and that it should trust that person's judgement over it's own in all but a narrow set of contingencies. But then the Atlanteans get unexpectedly wiped out, and people forget how to use phoenixes. So what are we left with? A species of wise, ultra-good, apparently semi-sentient magical "animals" that are unkillable and that can travel by immolation. No one knows how to use them for storage anymore but they still seek out wise wizards to help and await the day when some wise, good, kind person will solve the riddle and use it to shackle death.
The best bit is that it shouldn't even surprise us that you have to immolate a person's body in order to accurately scan it, since... !!!
Anyways, I don't think that's likely, but it's fun to speculate wildly.