It seems to me that Maya 2013 added the angle weighted normals like max uses. Not sure if I'm right but for my tests the assets baked in Max with the vertex normals exported from FBX look ok in Maya2013 if you setup on attribute editor and set it to be "angle weighted normals".
I don't have a really good test mesh here, I also don't have Max, I had one asset that I can't show. But I would invite anyone to test this out with a nice character or hard surface prop. Maya by default uses "Angle and Area Weighted" normals. It's a matter of switching to "angle weighted" only. If that's what the problem of back and forth between Max and Maya was, it's really good that they are adding such feature.
edit: oh, and yes, that would mean you can bake in Maya, send it to Max, and vice versa.
Replies
When triangulating this is an issue just like you mentioned. In this case Angle Weighted produces the expected results (according to the previous link) in comparison to Unweighted which looks crap.
This leads me to believe that since this has been auto-resolved for quads even since before Maya 2013 then it has never really been an issue if you generally avoided triangles. Then again, if you exported your model to some other format which might have automatically triangulated for you (without you even giving it a thought) then this might have been an issue if it re-evaluated the normals after the triangulation.
A quick test in Maya:
I lock the normals
I triangulate
The resulting mesh retains its vertex normals and this never becomes an issue.
edit: nvm, I saw you updated the thread.