Ok, another update.
I did play around with Printrun/Pronterface and things look grim :/
There seems to be significant play with my z-stage. Check out this short video:
I used printrun to move the bed around and after homing the z-axis and entering "G0 Z0", that's where the bed was at:
No way this would touch the nozzle...
I then moved the head around (by hand), alternating between Z30, Z0.1 and Z0. On the left side I have this with Z0:
And on the right side:
And the thing that sucked most - when I tried Z0 at the center I got the optimal distance from bed/nozzle (none...)
So my z-stage shifts around for whatever reason. I checked for loose screws or other oddities but didn't find anything.
By the way, if you use Printrun, don't forget to home the z-axis first or else it won't accept any gcode instructions regarding z-movement.