Most of the tools that are asked to automatically operate on mesh elements (faces, vertices, edges) depending on their visibility on the current view have this issue.
You'll experience the same thing for example by circle/lazo/box-selecting a dense mesh while in solid-shaded mode, or using the gradient/paint tool while weight painting.
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/V5PGX.png)
On the top right a box selction in Solid mode, while on the left a selection made in Wireframe mode.
I'm not qualified to tell exactly what's going on under the hood of the source code, so I'll suggest to take the following lines as my personal thought
As elements share more or less the same location on the screen because they are one next to each other, it is difficult for the software to exactly tell if one of them is there or not. From the pattern created, that shows a "quantization" of selection, I can guess that the algorithm is probably checking whether a element is falling inside one of the pixel cell of the selection/brush. Mix that with some numerical approximation and the result is that some of them are missed.
In addition you are doing that in solid mode, so the software has to take into account element's visibility and face's normal thereshold that make things usually harder.
My personal solution, when possible, is to paint/select while in "wireframe" mode or draw a shape and fix error from a closer view.
As currently (Blender 2.77) there is no option for going to a 3Dview-like wireframe mode (where you see behind solid faces, I mean, because wireframe mode for weigt &vertex paint means: "please, show me the wires"), you must look for custum build like this one where the creator has added an useful "limit selection to visible" option for vertex paint mode too.
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/Ls5bP.gif)
W
> Remove Doubles); check if geometry of the mesh is real, i.e. adjacent modifiers like Subsurf etc. are applied. Other than that please save a small part of problem object, upload the file and edit your post with a link. $\endgroup$