I've been trying to figure this out for a little while. I've been writing down my thoughts on the task in my devtalk post. Brecht has helped me with this, too. It seems pretty straightforward, and it looks like it won't involve any changes to Cycles at all, but rather to Blender. This would also mean vertex color baking in other engines that support baking, if I understand the code correctly. I haven't made much progress on the problem myself, I'm kinda waiting to see what the multi-res baking code will be as multi-res is refactored this year.
The biggest design problem to me is, how to handle objects that have generative modifiers? Pure deforming modifiers are easy enough to handle, since the vertex indices do not change, but generative modifiers add new vertices, take some away, change things around... should vertex color baking not be supported in these cases? Is there a way to save vertex color for the final, evaluated data instead of the actual mesh data? How complete should this feature be before it's in the master?