It seems like only one quad of vertices per pixel of my monitor got painted. Do you have any idea on how to get around this annoying effect?
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.
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.