Just to be clear you are backing the screw at the narrow end of the gib out before you tighten down the screw on the wide end? If you don't do that then you jam the gib into the other screw and warp it so the friction goes way up but the fit still is loose. If that is not the case I would remove them and check for debris or warping and proper orientation.
I can easily adjust mine to run real smooth with under a thou of deflection detectable. I can't get much better than that though or it becomes VERY stiff on the extremes of the travel and prone to stick-slip. The Z is just a pain. Best way I was told was to remove the lower gib adjustment screw and run the head down to a wood block on the table. and rest it against that to relieve the pressure. Now adjust the tob gib screw till it is snug but the head still moves up and down without stick slip and then snug up the lower gib screw to just touch. That was as good as it was going to get and it still nods just a bit and tends to move the spindle around if the lower lock is set.
The column mating surfaces should be clean of paint. That said on my PM-25 there was some bleed through that I cleaned off after the first take-down but I don't think that was really causing a problem. Still I cleaned it off because I sure didn't want to repeat the process of squaring the column any more than I had to.
CNC: Making incorrect parts and breaking stuff, faster and with greater precision.