that's one of those - 'it depends on what you want to do' questions.
For example; most robot arms have little pneumatic or hydralic cylinders on them. But keying the cylinders would be difficult and time consuming. So what you do instead is set up a couple of aim constraints to keep the two pieces of the cylinders pointed in the right directions. Then all you need to do is animate the arms, and the cylinders follow along, dynamically expanding and contracting as needed. (well, that's the basic setup, anyways).
There's about a million and 1 examples, for a million and 1 ways to do something. If you gave me an example, I could maybe give you an idea, but this machine doesn't have maya at the moment....
Actually, for deforming shoes for table 'contact', your best bet is probably going to be using the soft-selection tool. Although, again, depending on viewing angle and distance, you could probably get away with actually letting your feet intersect the table just slightly.