I think I have found a solution. As I already posted, I moved the PINDA probe closer to the bed surface and did a full alignment, I then took https://www.thingiverse.com/thing:2780118
and printed it - without modification this printed smooth on all 5 surfaces. I then moved the 4 outer squares to the edge -5mm of top/bottom/left/right and it showed 3 of the 4 corners had issues.
The solution was to manually adjust the bed upwards a bit by loosing the screws on the bed. This was a surprise, as I expected the calibration to do that, in particular in one corner where I adjusted more than 1mm upwards. But I wanted to share my solution so others may get a tip on solving this kind of issue.
With those two changes done, the very clear diagonal lines went away - you can no longer feel a clear difference on the surface, and all test surfaces are super super smooth (like printing the PRUSA logo's first layer).
So it looks like the auto-calibration was very good at the center part of the bed - all the way to about 3cm from each edge. From there I've had to do the calibration print above, and manually adjust until all the extreme squares were printed well.