I think you've lost sight of the fact that this entire discussion is constrained to the 4x4 matrices used in computer graphics. How to best invert a matrix of a particular small fixed size is a very different question from how to best invert matrices in general.
While true, there is a reason that the GLSL standard includes builtin data types for matnxm for all n,m in {2, 3, 4}. The single most common matrix operations in computer graphics are related to linear transforms on color spaces and geometry. Both of those max out at transforms on 4D vectors, for RGBA and 3D projective geometry.
