The Champions of Darkness (Oct. 2002) feat Hollow (43) seems to assume—although neither is a prerequisite for the feat—that the creature that possesses the feat both was born to a race of creatures that normally possess a soul and will remain soulless. This, in this DM's opinion, a creature that possesses the feat Hollow and that gains a soul during play—through whatever means—loses both the Hollow feat's substantial advantages (the creature's immunity to energy drain, possession, and soul-trapping effects) and its disadvantages (the creature's inability to be brought back from the dead).
In other words, this DM thinks that a creature that possesses the feat Hollow that gains a soul just isn't hollow anymore and that the feat then simply takes up space on the player's character sheet. (This DM would point the player to the Player's Handbook II rules for Feat Retraining (139) so that the character could replace feat Hollow with something now useful.)
Also, in a traditional nonravenloft dnd-3.5e campaign, living creatures without souls typically just don't exist. That is, while a living creature can totally bargain away its soul—like by making a Faustian pact (Fiendish Codex II 23-5)—, that usually means when the creature dies the creature's soul ends up where it normally wouldn't've. Not having a soul is typically one of the defining features of a creature that is not living, like a typical creature that possesses the type construct or the type undead.
In other words, the effects of the feat Hollow are effects the author believes are appropriate to a creature that lacks a soul—and, of course, actually are appropriate in a ravenloft campaign—, but, so far as I'm aware, there's no general description in Wizards of the Coast material for living creatures that lack souls and, by extension, usually rules are unnecessary for grafting a soul onto a still-somehow-living creature that's lost its own or never had one (cf. magic jar, soul bind, trap the soul). In short, the presence of the feat Hollow in a campaign setting that's not Ravenloft means that the campaign's sailed into uncharted waters.
Finally, on a technical level, shedding the feat completely via the aforementioned feat retraining, the dark chaos feat shuffle, the 4th-level psion/wilder power psychic reformation [telepathy] (XPH 127), or similar means may be enough for the DM to rule the creature's soul restored… or not: in a role-playing heavy campaign, absent a decent explanation for having gained a soul, the creature still was "born without a soul" even if the feat's gone from the character's sheet. A player should definitely ask the DM instead of assuming crossing off the feat means gaining a soul!
That said, this reader can imagine one possible way to grant forevermore a previously soulless creature a soul. However, as should be expected, it's a bit of a hassle.
Get a soul by becoming a construct then incarnating
A construct that's the subject of 9th-level Sor/Wiz spell incarnate construct [trans] (Savage Species 67-8) typically sees its type changed to humanoid. Thus when such a once-construct,-now-humanoid dies, it dies like a humanoid, and, when it's brought back from the dead, it's brought back like a humanoid. In a typical campaign
When a living creature [like a construct that's become a humanoid via the spell incarnate construct] dies, its soul departs its body, leaves the Material Plane, travels through the Astral Plane, and goes to abide on the plane where the creature’s deity resides. If the creature did not worship a deity, its soul departs to the plane corresponding to its alignment. Bringing someone back from the dead means retrieving his or her soul and returning it to his or her body. (171)
Without DM intervention, this seems to happen for the incarnated construct even if, prior to being the subject of the incarnate construct spell's effect, the construct didn't possess a soul! Thus it seems to this reader that the incarnation process bestows upon a construct a soul. I mean, the spell incarnate construct, after all, is a 9th-level spell with a casting time of eight hours that also has a gruesome material component (this DM assumes—even though the game doesn't—that "[t]he heart of a humanoid that has been dead less than 8 hours" is not in your spell component pouch!), so the spell's kind of allowed to be awesome.
(Exactly where this new soul comes from is rife with speculation—see answers to this question, for example,—, but Bastion of Broken Souls and Manual of Incarnum provide some information about preincarnate souls, so that's one canonical possibility. However, keep in mind that you're trying to get a soul into a body that's taken a feat from a third-party Ravenloft campaign setting sourcebook, so you're kind of on your own here and that could totally be a crossing-the-streams kind of bad for the creature!)
Thus the creature that possesses the feat Hollow that gains the type construct (see below) and becomes the subject of the spell incarnate construct could then perhaps gain a soul. That's because a construct as an unliving creature lacks a soul, whether or not that creature even had a soul before becoming a construct, and, after it's the subject of the spell incarnate construct, the creature typically becomes a humanoid, yet not the same humanoid it was but one with the template incarnate construct (SS 116) therefore a new being with—perhaps—a fresh-from-the-oven soul. (Not inconsequentially, this, too, should also cause the resultant creature to lose the entirety of the Hollow feat's benefit.)
However, while this process could see the creature gain a soul, the creature now has the template incarnate construct, and that means the creature loses all the special attacks and special qualities of the base creature it was prior to incarnating—and the player should ask the DM well beforehand if this includes special abilities gained from class levels!
Anyway, a DM nonetheless could (even reasonably, in my opinion) rule that all this will be for naught and that the resultant creature—for whatever reason (uncharted waters, remember?)—still will have no soul. Adventurers considering this technique should research it beforehand lest the prodigious resources the technique requires be wasted.
How to do that
A creature that has attached to it an additional or replacement golem limb (Monster Manual II 209) and that fails the subsequent Will saving throw (DC 15) gains the appropriate half-golem template (209-12 et al.) that instantaneously changes the creature's type to construct. Since it's not a spell effect, the creature can't voluntarily forego the saving throw against the golem limb, but it should be trivial to round up penalties on the saving throw sufficient that there's only a 5% chance succeeding on the Will saving throw. The cheapest golem limb—a flesh golem limb—has a price of 10,000 gp. Then it's a matter of finding a level 17 wizard capable of casting the spell incarnate construct on half-golem creature… somehow. Such a service—which isn't usually available due to the price (PH 129)—costs 26,530 gp, but it's also usually impossible: the half-golem creature's extraordinary ability magic immunity typically prevents from working on it the spell incarnate construct as the spell checks the subject's SR. (How the sample incarnate construct, a former stone golem (SS 120-1), came about is a mystery.)
The other way sees the creature acquire an arcane scroll of body of war [trans] (Spell Compendium 35) (7th-level spell at caster level 13) (2,275 gp; 0 lbs.) and an arcane scroll of incarnate construct [trans] (Savage Species 67-8) (9th-level spell at caster level 17) (28,825 gp; 0 lbs.) then spend 6,100 gp and 244 XP to use Gremma's cauldron (Expedition to Undermountain 217) (5,000 gp; 0 lbs.) to turn the scrolls into potions then consume the respective potions in succession, the specific rules for the cauldron presumably overriding the general rules for potions. (Similar yet less expensive workarounds that yield like results do, I'm certain, exist, but I'm a big fan of the cauldron and its myriad possibilities.)
"Is there another way?"
Not that I've found. For instance, this DM does not feel that just changing the creature's type, suiciding, then being brought back from the dead is sufficient to ensoul a soulless creature. That is, in such a case, no effect has been employed that would seem to this DM to change the creature's soul's status and, instead, only its form. (This DM would rule that, for example, such a creature still couldn't be brought back from the dead.) So for this DM it'd be a nonstarter to use a similar process—cast, die, raise—while affected by, for example, the 1st-level Drd spell aspect of the wolf [trans] (Spell Compendium 16-17) that changes the creature's type to animal, the 1st-level Sor/Wiz spell aberrate [trans] (Book of Vile Darkness 84) that changes the creature's type to aberration, or the 2nd-level Sor/Wiz spell essence of the dragon [trans] (Races of the Dragon 112-3) that changes the creature's type to dragon.
Even the much-vaunted and otherwise-all-purpose 8th-level Sor/Wiz spell polymorph any object [trans] (PH 263) isn't much help here: its duration is only permanent, never instantaneous, therefore rendering the effect vulnerable to dispelling, and, more importantly, the spell possesses the descriptor polymorph, which says, "If the subject of a polymorph spell is slain or rendered unconscious, the spell ends" (Player's Handbook (2012) 320). And the polymorph any object spell—with its merely permanent duration—is no exception to this.
Note: In campaigns I run, keeping someone dead is sometimes an issue, and squirreling away the creature's soul is a good way to do that. Hence getting a creature a soul without needing the original soul has been a real topic of conversation, and turning the creature from what it was into a construct then into a subtypeless humanoid that possesses the template incarnate construct has been pitched as a possible solution but never actually tried. Thank heavens.