Yes you can keyframe separate elements. I'm not talking about a separate animation system.
For rigid animations where you don't need mesh deformation (like a gun), there is absolutely no reason at all to use either the skin or physique modifier. (And no you can't keyframe individual verts in game engines, for this you WOULD need to use skin or physique).
But you MUST have a linked heirarchy BEFORE you start animating with keyframes. Open the schematic view in max, and decide which object will be the parent. For a gun, this will be the main part of the weapon, all moving parts will need linked to this and will be the "children", the children will inherit the transforms of the parent. Another example would be a animated door. The door is the parent, and the dooknob would be linked to it as a child object.
Linking can be done in the schematic view. It is important to set up your heirarchy BEFORE you start keyframing, or else it WILL get screwed up on export. And if you don't set up a heirarchy, then the animation will collapse to the root node and you will lose parts of it.
Now, you CAN link objects together from the main view in 3ds max (the buttons are right beside the undo/redo buttons), but it's far more intuitive to do it from the schematic view, which shows a nice visual representation of a "family tree" showing how the objects are linked.
I'm going to bed now, but if you still have problems I can upload one of my max files from Model Pack 2, a door or the animated safe would be a good example.
EDIT: And one thing I should add, for these rigid model animations such a gun, it is VITAL to reset X-forms BEFORE setting up you heirarchy.
So...the workflow would be something like this:
1. Model the parts of your gun (each moving part will be a separate model).
2. Set the pivot points on each model where you want them for easier keyframing.
3. Reset X-forms
4. Set up your linked heirarchy
5. Animate with keyframes
6. Export