Remove doubles distorts mesh aspect in object mode (still good in edit mode)
This should be correct. By default Blender displays wireframes based on the angle of the faces connected by a given edge. In order to have blender show all edges you have to check "Draw all Edges".