I have the problem that on every start of kmail, the first column gets a pixel more than before, leading to my "date" column becoming smaller and smaller.

To fix this, it seems to be enough to ensure that when the columns take their sizes from the widget, to keep the fractional part of the column widths.
E.g. after the auto-calculation of the widths a column might have 100.3 pixels in width, however the .3 fractional part is lost when the column width is taken from the widget since the widget only stores int values.

Started kmail several times and checked via kruler and kmag that the columns kept their size exactly