In max3, it was no contest: both Physique and Bones Pro were just better than skin. Skin in max4 however has me rather torn. Now, it's a case by case call whether I'm going to use skin or physique on a character.
Vertex weight assignment in skin still has a few hardcore features that need to go in, most notably an inspector, some way to see the weight of every vertice vs every bone in a spreadsheet, but vertex assignment is now very doable, and in my limited experiences in the few months max4 has been out, actualy faster than in physique.
My skin workflow is first to set envelopes. Envelopes get you 60-70% of the way there, especially with lower vert count models, say if you're skinning before Nurms. After you get the envelopes just right, and you know your geometry is locked down, the next step is any obvious exclusions. Getting the spine out of influencing any verts on the arms that happen to fall close to the body is a start, and excluding each leg from the other is next. At this point, I'm usualy 80-90% of the way there. Next, it's just a matter of going through each bone sequentialy with the shaded view on, and picking stray verts and explicitly assigning a weight with the spinner. A little tweaking at joints going back and forth between bones is usualy all that's needed after this. I very rarely use the paint tool, other than if I have to cover lot's of ground, like if I'm boning a facial setup. Painting is a great way to handle a really dense mesh, but I try to keep mine down, and until now have been able to work with low poly cages, and Nurms on top of that, and with this setup, I'd rather have more tools focused on being able to easily adjust individual vertices.
Now, the thing about Physique is, well, it's splines. Joints look naturally better with Physique, where with skin you're almost guaranteed at least having to use a few angle deformers, with Physique, once you're weighted, your joints are probably already working well, with no loss of mass. But weighting in Physique can take longer, as the display seems to me a little more sluggish (bear in mind I have a slow 'puter here), and the assign vertex weights tools are a little clunkier.
So it's either way really. I like both for their strengths, and will probably continue to pick one or the other on a per character basis.