Did some further testing here:
1 - One side booleaned
2 - One side booleaned and mirrored (and re-uved)
3 - One side has 34 faces on the loop going around the cylinder, other side has 25 faces
4 - One side has 68 faces on the loop going around the cylinder, other side has 25 faces
1 - Bakes with no artifacts on top face
2 - Bakes with no artifacts on top face
3 - Bakes with artifacts on top face
4 - Bakes with artifacts on top face
(This is the face loop I’m counting faces on, btw -)
They were all triangulated before the bake (modifier off on screenshot for clarity). Also baked without triangulation and just the ngons and got varying results, but still artifacts in 3 and 4.
The number of faces doesn’t really seem to matter, but it looks like they need to be the same in order for it to create the smooth baked result.
mrgesy’s mesh from the .blend attached to their OP has 99 faces on one side, and 126 on the other, so this is consistent there too. If you boolean 2 different cylinders with different edge counts out of the top of a cube like there and get a result that doesn’t have any artifacts, I definitely want to know the sorcery 
At any rate, in the interest of not “spamming” this thread, I won’t post more about it after this, but it looks like we may have found the limitation with it here.