Before tearing the machine apart Richard, have you confirmed that the lean causes a problem in practice? Although you're probably right, it's remarkably easy to be led astray by when testing machines, and also easy to misdiagnose causes. If it ain't broke, don't fix it.
Also, if you haven't already done so, check everything. For example, does the DTI in your test set-up register any movement when you push the column?
It may be you have a wrongly ground table from new, but that seems unlikely. It could be due to wear, but the table top being clean suggests otherwise. Unless, that is, the top was reground badly in the past by a dodgy salesman to make it look good! Most likely, I feel, is that the column/head has moved in transit and you may be able to fix it by shimming.
I think it's worth spending some time checking work made by the mill, and also taking more measurements to pin down the cause. Apologies for wasting your time if you've already done all that!
Dave