Halivar,
I didn't have the "walk-off" problem, but some of the "solutions" advertised here were just as problematic.... continually adding on to a PC to power them up is symptomatic of a lot of 3.x games... especially now with 3.5 and all those d20 supplements flying around. As a DM I had to outlaw most material except for core, then I had to redefine "core" as players argued anything with a WOTC logo counted, and I still had half-dragon mages for pcs....
This is why I moved away from the whole 3.x path and embraced Castles & Crusades. The basic focus difference here is simple: older D&D and C&C=slower progression and WHO the characters are, 3.x and much "d20" logo material = fast progression and WHAT your character can do. Your players there are so fixated on the latter that they get caught up in the endless class, feats, templates and other junk that they never care WHO the character is, just what they can do, and that's why they get bored and want to change up.
I know, I know... people around these parts call me crazy and say 3.5 is balanced, it was 2e that was overpowered, etc... but there is something here no one wants to admit - WOTC (and this is bandied about ad nauseum on the 4e threads) is in this to SELL books... the game is indeed designed to progress characters rapidly so that DM's and players have to buy supplements to "improve" the characters or "balance" the encounters. Unless you markedly change the nature of XP and progression, characters almost always seem to go up a level per session early on, then it slows just a bit as you reach higher levels (at which point characters are adding prestige classes and templates to up the power quotient).
So Halivar, I invite you to turn from the Dark Side....
Check out other systems, including C&C, and find some players who aren't powergamers. Most of the posts here have no sympathy because they agree - and that's all cool, but it's not what you want obviously.
I do agree with the DM's responsibility here - although I find it interesting in context of the numerous other threads that argue for "DMless" D&D, giving Players more power over the game, or essentially all the DM should be is a "facilitator."
Sincerely,
John