This behavior of a mesh is almost ever an issue of either "zero weighted" vertices or "ungrouped" vertices. To clarify:
Zero Weighted Vertices
Vertices which have entries in one or more Bone Weight maps, but the sum of all weights is 0. This can happen when all weights for a vertex have been painted to a value of 0 (blue).
Vertices which have no entries in any of the Bone weight maps. This can happen when you manually removed weight entries from some of the weight maps, or when you cleaned up your weight maps with the limit weigths tool.
Finding the locations of problematic vertices
when you are in weight paint mode, then you can open the tool shelf, locate the Options vertical tab, and set the value of Show Zero weights to All
Then all areas with unweighted vertices or with vertices with a weight sum of 0 will be rendered in black.
Note: You can change the color from black to something better visible. I changed the User Preferences -> Themes, in the 3D View Section: set "Vertex Group Unreferenced" to your favorite color (i used Magenta):
Selecting ungrouped Vertices
In edit mode, in the Footer of the 3D View: Select -> Ungrouped
Then all vertices will be selected which are not mentioned in any vertex group: