I have been working recently on a problem that appears to be related, namely, maximizing the absolute value of the determinant of a chosen $m\times m$ submatrix $S$ of a $m\times N$ submatrix $V$ (think to the columns of $V$ as your vectors). I can tell you the following.

• Finding the maximum volume submatrix is an NP-hard problem, so I guess that your problem may suffer the same fate
• a useful relaxation, however, is finding a submatrix that has locally maximum volume, i.e., larger than all those that can be obtained by changing one vector only. There is a paper by Knuth (yes, that Knuth) that studies the problem. The interesting feature is that in this way the matrix $S^{-1}V$ has a submatrix equal to the identity matrix (obvious) and all other entries bounded in modulus by 1. This is enough to ensure good conditioning, at least in the applications that we were investigating. One can prove that the rows of the matrix $V$ are a well-conditioned basis for its row space, for instance. Another reference is this paper.
• a second relaxation is finding a submatrix $S$ such that $S^{-1}V$ has all entries bounded by some real $\tau>1$. This problem can be solved explicitly in $O(Nm^2\frac{\log m}{\log\tau})$. The good conditioning properties carry over to this relaxation, up to a factor $\tau$. Putting everything together, I think that one can prove using the techniques in our paper that the matrix chosen by the algorithm has conditioning within $O(\sqrt{Nm}\tau)$ from the conditioning of the rectangular matrix $V$ (defined as largest over smallest singular value), which is a theoretical maximum for the conditioning of $S$ (I think).
• if you have a practical computation and you want to check how things work with this solution, I have some Matlab code in a packaged and usable state that you might wish to try out. Feel free to ask for explanation if the documentation is too poor.

I have been working recently on a similar problem, namely, maximizing the absolute value of the determinant of a chosen $m\times m$ submatrix $S$ of a $m\times N$ submatrix $V$ (think to the columns of $V$ as your vectors). At first sight, it may seem that the two problems are not related, but one can prove that if $S$ has this property then $S^{-1}V$ has all entries bounded in modulus by 1. This is enough to ensure some form of stability, at least in the applications that we were investigating, and I suspect that yours case might be similar. Other useful references are this paper and this one. 

I can tell you the following.

• Finding the maximum volume submatrix is an NP-hard problem, so I guess that your problem may suffer the same fate
• a useful relaxation, however, is finding a submatrix that has locally maximum volume, i.e., larger than all those that can be obtained by changing one vector only. There is a paper by Knuth (yes, that Knuth) that studies the problem.
• a second relaxation is finding a submatrix $S$ such that $S^{-1}V$ has all entries bounded by some real $\tau>1$. This problem can be solved explicitly in $O(Nm^2\frac{\log m}{\log\tau})$. The good conditioning properties carry over to this relaxation, up to a factor $\tau$. Putting everything together, I think that one can prove using the techniques in our paper that the matrix chosen by the algorithm has conditioning which differs by at most a factor $O(\sqrt{Nm}\tau)$ from the conditioning of the rectangular matrix $V$ (defined as largest over smallest singular value), which is a theoretical maximum for the conditioning of $S$ (I think).
• if you have a practical computation and you want to check how things work with this solution, I have some Matlab code in a packaged and usable state that you might wish to try out. Feel free to ask for explanation if the documentation is too poor.