I think I have finally solved the problem. One commonly recommended solution is to use vertical-align: middle:
<input type="radio" style="vertical-align: middle"> Label
The problem, however, is that this still produces visible misalignments even though it should theoretically work. The CSS2 specification says that:
vertical-align: middle: Align the vertical midpoint of the box with the baseline of the parent box plus half the x-height of the parent.
So it should be in the perfect centre (the x-height is the height of the character x). However, the problem seems to be caused by the fact browsers commonly add some random uneven margins to radio buttons and checkboxes. One can check, for instance in Firefox using Firebug, that the default checkbox margin in Firefox is 3px 3px 0px 5px. I’m not sure where it comes from, but the other browsers seem to have similar margins as well. So to get a perfect alignment, one needs to get rid of these margins:
<input type="radio" style="vertical-align: middle; margin: 0px;"> Label
It is still interesting to note that in the table based solution the margins are somehow eaten and everything aligns nicely.