I'd go with Outsider for the creature type. Based on your description of where the creatures come from, they're essentially transformed petitioners put into their new existence based on their actions in life. That's where most fiends (evil outsiders) come from in D&D.
I'd say this is the part of the Outsider description that seems most applicable:
Except I purposely put the bit about 'reincarnated' which allows them a new body with the same soul. Those who are the recipients of a reincarnation spell are not outsiders for instance.