I imagine that if you lose your soul, you also lose access to the gods. For paladins and clerics at least, that's the whole kit-and-caboodle.
But also to the extent that gods and religion are significant to the plot, it could be a real handicap if, say, not having a soul makes you basically invisible to the gods and their agents. I would also expect some especially pious NPCs to notice the lack of a soul, and any who have experience with evil might be likely to conclude that the PC is not a human/elf/dwarf/etc, but a monster in disguise.
Mechanically, holy spells like Turn Undead could very well also turn a PC who has no soul. Perhaps such a PC becomes vulnerable to Radiant damage, takes damage instead of healing from holy powers, and is unable to enter sacred places or tread upon hallowed ground. Perhaps a PC without a soul is, for all intents and purposes, undead.
And, who's to say what "natural" processes depend upon the soul? Perhaps the body of a mortal begins to decay once its soul is taken away, and the afflicted is now forced to resort to drastic and artificial means to keep themselves together. (Did you ever see Death Becomes Her?) I would definitely expect physical characteristics to suffer, especially Constitution. Perhaps the scores stay the same, but the modifiers swing toward the negative.
Finally, what about the impact on the PC's personality? Without the soul to tether their psyche, I imagine the freshly-undead will suffer from progressive Charisma penalties (and that's to say nothing of how visually off-putting it is to NPCs when you present as a leper, your skin has the pallor of a corpse, and your breath carries the aroma of a freshly-dug grave).
And then there's Grave Madness. As the mind recoils in horror from the walking meat sarcophagus it is trapped inside, the PC begins to see things: flashes of things that aren't there, glimpsed scenes of morbid depravity and inhuman torture. One stops recognizing the faces of their companions, and begins to see flesh and sinew stretched taught over bones, hollow automatons jerking awkwardly in a cruel parody of the living. Voices sound distant, food loses its flavor, and everything always so cold... There is no telling what someone seized by Grave Madness might do in their extremity.
I see penalties to skills like Diplomacy (distracted by visions, preoccupied by a feeling of alienness, hard to even understand what others are saying), Deception (loss of awareness of one's surroundings, inability to read facial expressions), Insight (monomaniacal fascination with the visceral).
On the other hand, I see the potential for bonuses to other skills, depending on how they are played, primarily History (morbid visions could be based in fact), and Intimidation (legit able to creep people out, and be outright terrifying for anyone who mistakes the absence of a soul as a sign of being a monster).
I guess what I'm saying is: if your party is unable to imagine negative consequences to losing a soul, it's possible they've been watching too much Twilight and not reading enough H.P. Lovecraft. ;)
I seem to recall that the Raven Queen is all about bringing death to the world. Perhaps she begins to take an active interest in a PC without a soul. That could be a bad thing.