By using smooth shading (i.e. interpolation of normals), an object can have a smooth look despite low polygon count. A nasty artifact that can happen when casting shadow rays is the Shadow Line Artifact. Since shadow rays originate from a certain position and don't usually take the normal into account, a complete face on a smooth object will either be shadowed or not, revealing the hard edges again:

The shadow is, so to speak, 'correct' and the weird appearance results from the normal map interpolation 'cheat'. Nevertheless, it is visually distracting. The linked article above, written in 2009, suggests removing shadows or self-shadows on objects that show this kind of artifact, which (especially for non-convex objects) is not a satisfying solution.

This is a very common problem inherent to ray tracing algorithms. I wonder if there is any better solution to it than subdividing the mesh into flat-shaded high-poly or getting rid of the shadows altogether.

The shadow terminator problem (as it's also known) is still something of an open problem in ray-tracing. As you say, disabling self-shadowing is not a very good workaround, because non-convex meshes often need to self-shadow. There's a possible refinement to this method. Instead of throwing away all shadow ray intersections with the same object, you can only throw away the intersection if it's with the same object and it's through the reverse face of the triangle (i.e. discard the intersection if $d\dot\ N > 0$, where $N$ is the geometric normal of the intersected polygon and $d$ is the shadow ray direction).
You should also be sure to use the normal rather than the geometric surface to decide whether the light is "behind" the surface. That is, if $N\dot\ L < 0$, the shading point is in shadow (without needing to cast a ray), where $N$ is the interpolated and shaded normal.