Nice one - some good reading.
Yep Gimbal is a pain in the behind... the solutions posted here are pretty cool. There are a couple of ways around it, some of which depend on the software I guess (ie the TCB thing suggested here for Max).
The first thing I would look at when I rig is the order of rotation and get something that 'makes sense'. (Not sure if you can do this in Max, but basically you can dictate which rotational axis gets computed first.) Not always easy, especially in shoulder areas.
Another thing I tend to do when rigging, similar to what Peter suggested, is to build in null objects. Like a parent object above the main control which I can access if I need to get myself out of a gimbal situation.
As a last resort I'll just key on every frame and 'beat' the gimbal issue. I'll wait till I'm near the final stages of the anim of course, but really, the only reason you get those funny arcs is because the computer is a bad in-betweener - don't be afraid to go a bit traditional and key every frame!