I can answer this for Blender at least, but maybe it'll give a hint for 3D Max too. When you're weighting the parts of your mesh to bones in your armature, it's assigning a value of 0 (no influence), 1 (total influence), or somewhere in between to each vertex. It seems like all vertices must be assigned to at least one bone, even if it's just a static "this item doesn't move" bone.
Using weight paint in Blender is kind of imprecise for this, but in edit mode, you can see the actual weight value for each vertex in the right-hand properties menu (which you open by pressing N from the standard 3D view). Each vertex will need to be assigned a total of 1 weight to one or more bones (1 to 1 bone, or 0.5 each to 2 bones, or 0.25 to one bone and 0.75 to another, etc.). No vertex can be assigned a total of more than 1. Here's what it looks like (I also have "Show Weights" enabled, which can be found further down that same menu, under Mesh Display):
I hope I'm explaining this right - I'm still rather new too, but this is how I fixed this error for mine!
Also, I believe this check and error is kinda new, as I had a model that had vertices with no assigned bone which was working a few days ago, but suddenly stopped working with this same error until I fixed the weights.