Some good ones have already been mentioned so I'll offer some twists on thoughts already said ...
A curse. The curse can be mechanical (penatly to skills/stats) or more flavorful for RP purposes only - or both, depending on how severe you want. For mechanical curses you can see the curse spell for examples (or any spell that mimics curse effects or requires the same spell to dispel as a curse spell does). For RP type curses, they grow hair at night (maybe some minor charisma penalty during that time) or something like that; even if it's not affecting them mechanically or during actions, any players actually into the RP aspect of it will feel the 'sting'. You can get curses as part of a magical trap for going into the wrong room, or for pissing off the wrong magical user/magical creature. Or they just wake up one morning cursed and have to figure out why and how to undo it.
A transformation of some sort. A transformation sort of ties in with the idea of a curse.. but maybe a transmuter attacks with some special spell and turns him/her/them into half orcs or goblins or kobolds or just really ugly versions of themselves (gaunt faces, dangly limbs -X to Charisma, etc), or they all get templates (fiendish type templates may make good type characters very uneasy

). This has social/RP implications as well as character stat adjustments... (and if very severely changed, their friends may no longer recognize or trust them) and it would be a few adventure sessions to correct it (finding the right person or item or whatever to correct it or breaking the mirror or staff that the transmuter used to alter their appearance, etc)
Limit use of stuff. The way to get around actually taking their stuff away is to limit it some how. Maybe the stuff was was in the area of a magical attack or trap resulting in a dispel-type effect, making magic items weaker (or fewer charges or a chance to backfire).
Incapacitate. He's not dead but he's stoned (har har) or his soul is trapped in a magic jar or he opened a book that now has him trapped inside. The player would need an alt PC or take over an NPC while the others quest to revive him. But in the end, the incapacitated PC will have less experience than the others -- unless everyone is incapacitated and using alt PCs for the resuce -- the penalty at this point is lost time. If the PCs are racing against some deadline in the story, losing 7 days in game when they only have 8 to stop the big bad plot, well, that's 7 days of counter measures they lost.... they won't actually feel that sort of sting unless there is a known deadline and also only if they had plans for what they would do during those days that will be lost. And if the alt PCs don't free the real PCs in time (the alt PCs being unaware of the other plots) then they could *fail* to stop the big plot.. and nothing stings more than failure.
Scorn. Whatever they did to illicit the penalty was noticed by someone that would otherwise have been their friend (or said would-be-friend heard through the rumor mill, etc). Maybe a particular cleric sect has heard of what happened and that one sect will no longer heal/help them. It turns into an inconvinience as you only need to go to the next cleric sect... but if they are into the RP elements of the story than they could feel like "ouch, we did something bad" if you need a mechanical element for this, make it a penalty on NPC reactions for anyone of whatever group you decide now dislikes them.
Death without ... it's D&D, so raise dead and DM actions are norms to keep people alive...I don't know how to offer this option without an example. I ran a campaign where I also didn't want to kill the PCs unless they did something stupid. Sure enough, they did something stupid that resulted in a total party kill in the middle of the forest. Feeling gracious, I had them all "wake up" only to find they were different. I had a druid reincarnate them all (he was fighting the same evil force in the woods and so wanted the allies) and so they came back as a variety of humanoid forms. Some players got into it (the stat adjustments, the appearance and social implications with friends and associates, etc) but one player did get very upset because his new form's stats no longer allowed the min-maxing for his characters strength-fighter type concept - so careful if you think that might be a result.
this is just a random two-minute brainstorm.. i know some of these ideas are rather weak and some work better in some situations than others. but if i think of anything else, i'll add more later.