Gonzaga has beat out bigger programs for a lot of guys. For example:
-Pargo: Offers from Illinois, Purdue, Arkansas.
-Heytvelt: Offers from Kansas, Wash.
-Sacre: Offers from UCLA, Wash, Mich.
-Downs: Could've gone almost anywhere (Duke, etc.) after leaving Kansas.
-Goodson: Offer from Oklahoma.
-Bouldin: Offers from Cal, BC, NC State.
Daye: Offer from Washington.
To say that they're signing mostly overlooked and over players is simply incorrect.
And yes, I agree that the coach retention problem is an issue at mid-majors. That has been discussed in this thread and others. I don't think that the engine should look purely at baseline prestige (there needs to be some weight to account for all the success), but finding a happy medium between baseline and current prestige would do the trick. (Most of those jobs have baselines in the D range.)
But the other issues are significant as well. When you can literally make the S16 and have your prestige drop, that is a problem, and one that should be addressed in some way.