Line width changes depending on the direction the print head moves
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!