I just re-ran all basic calibration steps from the Original Prusa i3 MK2 Manual.
Now, when doing the first layer calibration, lines that are running in positive X direction are ok, while those running in negative X direction are severely squished.
I already did Bed level correction, so each line is exactly the same width over its entire distance and tried to raise the live-adjust Z, but that leads to the thin lines not adhering at all. My printer is 100% stock, I modified nothing about it.
What can I do to troubleshoot this further?
As pointed at by @Horitsu, the Nozzle was the problem. Its outflowing hole was not perfectly round anymore, leading to a higher extrusion rate in one direction than others.
I exchanged it, and now everything works great again!