Anet A6, Marlin 1.1.x, bed leveling with sensor probe
Eventually it was a mixture of things that sort of solved this.

Setting the Z-offset a bit more tight helped some
Probing with more gridpoints helped
Instead of using glue, I used painterstape. Way easier to refresh and easier to take prints off. I wanted to try kapton tape, but painterstape was good enough for now.
Manually leveling the bed to a better position also helped.
(After edit) recalibrating my two z-axis motors.

In the end, I think my bed has become a bit curved over time. So a final solution would be to print on a glass bed, but that was not really an option when using the SN04 sensor.
I am moving now to a BLTouch sensor + glass bed to make everything perfect again.
EDIT: important note, I also put off bed heating. Since I am working with PLA, it was not really necessary. Doing this allowed me to use painterstape, otherwise it would 'fall off' eventually.
EDIT2: I think I have thought of a better explanation. I am using an Anet A6 and it might be because the x-axis was not parallel to the plate. Meaning that my two z-axis stepper motors were not calibrated properly.