If ssh starts going down that road, another dozen or so "special cases" later it'll be a horrible mess of magic interdependencies, with determining whether negotiation _can_ succeed bordering on NP-hard.
SSH is already down that road. GSSAPI key exchange requires ignoring the negotiated host key algorithm.
I think you're exaggerating the problem. denis