Is there anything they could do to give him a soul, just so they can get that soul when he dies, ending in a positive net-result of divine soul-fuel for them?
I know of no feat, power, or magic listed in 3.5 or 3.0 that will "create" a soul. There are things that can transfer a soul from one vessel to another but those are out in this situation.
Apart from intervention by some deity, your best bet would be a Wish (or other Wish like magic). Some may argue that even a Wish will not create a soul. Maybe yes, maybe no. I'm not going to debate that. You can look at this as a "cure" type wish or spin it as "resurrection-ish" like wish or maybe even as "undo misfortune" in that some awful cosmic accident or joke lead to this soulless state. However you spin it, I think that within the scope of what's defined in 3.5/3.0 Wish is about the best you can do.
Outside of that, I think story driven solutions are in order. A quest! In this case "the demons of the chaotic-evil afterlife" are looking for a way to give the PC a soul so they can later take it. The irony is not lost on me. Still, the story of it all could be great fun.