My interpretation has always been that a "regular mesh" implies a well-ordered mesh with minimal element distortion. For example, a swept hex-mesh is often very regular. Regular meshes tend to have low element distortion.
Likewise, a less-ordered mesh may be termed "irregular". An irregular mesh may have a higher degree of element distortion, and hence more built-in mathematical error. Tetrahedral elements often produce irregular meshes.
It's always important to pay attention to the shape of your elements. The solver is pretending that the elements are perfect cubes, tetrahedrals, squares, or equilateral triangles in order to obtain a numerical solution. Of course, this isn't the case. The more that the element deviates from those shapes, the more error you'll get in your answer.
Another important thing to realize is that FEA solvers find displacements first, then use those results to determine stresses and strains. So, if you get a bad result due to a highly irregular mesh, the derivative of your bad result will be even farther off.
At the end of the day, good FEA modeling comes down to having appropriate boundary conditions and a sufficient mesh in the appropriate areas to get good results. Of course, the devil is in the details... and bad FEA is, well... dangerous.