How to smooth a mesh?
Apparently there was something wrong with my mesh (although it looked completely fine in edit mode). I activated the Mesh: 3D Print Toolbox add-on and then used the Make Manifold button on my mesh. After that all the smoothing tools (Smooth modifier, Smooth sculpt brush) began to work properly.