Vertex Paiting slightly hidden parts of the mesh
I think that is not possible to configure the vertex paint brush with the options provided by Blender at this time (2.75a) without scripting yourself the tool you need.

The vertex brush simply cannot "see" the face, probably because it's normal is not facing the brush projection enough...or something like that...
I'm not a coder as you might have guessed, but I can suggest to you two alternatives workflows:

1-Texture paint-->Vertex Color


UV unwrap your model
Create a texture
Paint your colors on the texture
Install and use the Bake Uv-Texture to Vertex colors add-on


By painting with the texture tools you'll be able to access the "Normal threshold" options that make you able to define a custom range for your brush



Than you can extract color info from the texture map through the add-on and bake them to vertex color

Result:



2 - Edit mode, expand and contract selection


Go to Edit mode
Select faces
Ctrl+"+" to expand till filling holes
Ctrl+"-" to reduce selection to the initial size
Go to Vertex paint, set "face selection masking" on to work only on
the selected faces
Shift+"k" to paint the brush color on the active faces


This works only if you are using solid colours, without blending ramps on the border or other features that the vertex paint is able to achieve.

And of course you have to iterate the process for every different colour (and without the possibility to see what you have done before).

Before expanding and contracting selection:



After:



Setting color to selected faces in edit mode: