Prompted by a request in this BlenderArtists thread I created a small add-on that assigns random vertex colors to regions with connected vertices.
The image shows a single object consisting of several cubes. within each cube all vertices are connected and therefore get the same (but random) color.
The code for the functionality shown in this article is available on GitHub. use File -> User preferences ... -> Addons -> Install from file to install it and don't forget to enable the check box. It will then be available in the Paint menu in Vertex Paint mode.
For discussion you might want to check here