You could paint on the highpoly in ZBrush, export that as a OBJ with included polypaint(vertex colors?). Then use xNormal's "Bake highpoly's vertex colors" feature. I've had some quite successful results with this when generating curvature data. Not from ZBrush's polypaint though. Might be worth looking into.
intersecting meshes are fine. This isn't the same as floating geometry, which is usually used to refer to small pieces sitting on top of a high-poly surface. It causes weird artifacts primarily with vertex lighting...which few games do nowadays. And it isn't always an issue with vertex lighting, either.
.3ds only supports a single UV coord per vertex, so where ever there's a UV seam, the vertices will be split. If you still want to use .3ds, you can just re-weld the vertices in 3ds max. Easy... Sub-Object = Vertex, Select All, Weld.
Polypaint does not require uvs. As far as I know they can be exported as vertex colors but thats a per vertex base and most of the time it gives much lower resolution than a texture would. In a real world use, you need to properly uv the asset and use textures.
No, it's a separate issue. Long thin triangles can create uneven shading because the vertex normals aren't being interpolated very well. Baked normal maps rely heavily on well-formed vertex normals. We have some info here about modeling for baking: http://wiki.polycount.com/wiki/Normal_Map_Modeling Long thin triangles are…
UVs will not be affected if you have the same number of unique vertices between the two models. Each vertex contains as much UV information as faces attached to it. It's strange, because you may have one vertex but it'll have several UVs for all of its different faces.
Are you using the "Bake high poly vertex colors" option? The way I bake my ID mesh (probably not the most efficient way) Is that I color-code the high poly by each material then bake the vertex colors and make the resulting image my ID map.
I think you could make it happen by setting up a loop that checks each vertex against all the locators and then moves that vertex to the closest locator. My MEL is a bit rusty at the moment so I'm not going to hash together pseudocode till I get home.
Also you can try baking AO into vertex color. http://wiki.polycount.com/wiki/Ambient_occlusion_vertex_color If you use the VertexPaint modifier in 3ds Max, you can use the Blur function to soften the hard transitions. You can convert vertex color into a bitmap using Render To Texture, or Xnormal.
The error message has nothing to do with the polycount of your mesh. As the message explain, you tried to bake a color map (probably the ID map) with as input the vertex color, however the baker is unable to find them. Are you sure you exported vertex colors on the mesh you are trying to bake ?