The feel from what you said indicates that the problem is less about method length and more about the fact that they don't know how to use exceptions properly. Instead of requiring method length limits (which is fine, but really treats the sympton, not the problem), I'd suggest some standard guidelines around how, when, and where to use exceptions (and other things that may help solve the real problem). Otherwise, in order to comply, they made just break those some methods up into smaller ones with the same problem, and only make it worse (can you imagine those same methods being broken up into more methods, arbitrarily, with additional return value checks?).
Dan