The problem is, that you loose precision when you split your polygons.
I think one solution would be to reuse the same vertex (on the GPU) for polygons that have been split. So if you split polygon A into B and C then B and C will share two vertices at their split-border. If you then render B and C, both should index the same vertex in the vertex-buffer array. Because when you use the exact same vertex then two adjacent polygons should not produce such missing pixels.
PS: Well, T-vertices are of course a bigger problem. Hm, no idea right now.