This is where this add-on comes in handy: it will count the number of vertex colors used in all selected objects and reassign colors in such a way that all the colors are unique with the selected objects.
For example, starting with two meshes with identical color assignments
You will end up with something like this:
Note that none of the colors used in the left mesh appear in the right mesh and vice versa.
Availability
As usual the add-on is available for download from my GitHub repository (right click on the link and select Save as ...)After you have installed and enabled the add-on, a new menu entry will be available in object mode:
Object → Make vertex colors unique
.
It might be a bit odd not to have this in vertex paint mode but it operates on more than one selected object and selecting objects is not possible in vertex paint mode so this is a bit less inconvenient.