Well, if you want a solution that attempts to stay within the rules and does not rely on casting a "big wish":
1. Cast gate and name the target creature. It has presumably become some kind of petitioner (e.g., a lemure, manes, einherjar, etc.); gate allows you to reach that petitioner on the plane where it resides, and call it forth in its physical body.
2. True polymorph the petitioner into humanoid form. Maintain concentration for the full duration.
3. Kill it. Because true polymorph was sustained for the duration, the conditions for ending it have been overwritten with "until dispelled." So the petitioner does not revert to being a celestial/fiend/whatever on death. It remains humanoid, and is thus a legit target for:
4. Reincarnate on the remains. The petitioner is reincarnated as a humanoid. True polymorph can now be safely dispelled.
5. If you get the wrong race, kill it and reincarnate again. Repeat until you get the right one.
Of course, this presumes that the petitioner has not already been destroyed on its home plane in the interim. If it has, you're out of luck. Also, petitioners often get mindwiped, so there may be some psychic repair work required... in fact, there probably will be anyway, given that this scheme relies on murdering your target multiple times.
(Getting the players to understand that this is the villain's scheme would be a truly heroic feat of DMing.)