Complexity of deciding whether a matrix is totally regular
The paper Vandermonde Matrices, NP-Completeness, and Transversal Subspaces [ps] by Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran may be relevant to your question (though it does not answer it).

They prove the $\mathsf{NP}$-completeness of the following problem: Given an $n\times m$ matrix over $\mathbb Z$ ($n\le m$), decide whether there exists a $n\times n$ submatrix whose determinant vanishes.