So, I finally had opportunity to do some testing of the different behavior of ToElementMesh. I can confirm now that the same code produces different mesh when run on ver. 10.0 vs. 10.3

<< NDSolve`FEM
\[CapitalOmega] = 
 RegionDifference[Cylinder[{{0, 0, -3.13}, {0, 0, 3.13}}, 40.1], 
  Cylinder[{{0, 0, -3.13}, {0, 0, 3.13}}, 10.58]]
M = ToElementMesh[\[CapitalOmega], MaxCellMeasure -> 1]["Wireframe"]

On ver. 10.0 this produces nice mesh. On 10.3 This produces the square around the center hole that I showed in the OP.

Is this a bug?

This square is caused by so called spiders in the meshing. Spiders are considered in general as bad because the quality of the mesh determines the quality of the solution and a spider usually contains a lot of bad quality mesh elements. The mesh looks at all incomfortable, may be you take a deeper look into the reference pages and user manuals to find out the relevant parameters.

As far as meshing theory and practice is concerned, you may want to look into On boundary conforming anisotropic Delaunay meshes, the dissertation of Jens Krause (he is not a relative of mine, but was then a colleague of mine).