I'm going to go ahead and agree to the original overkill gib idea because I don't ALWAYS want to explode if I got killed by, say, a Gun or an SMG. However, rocket gibs are VERY satisfying and so I would say any damage over 110 would be a gib? Or even go so far as to just script it so explosions cause an instagib.
Another idea is to have a headshot code where if the last bullet before death hit the head, the head explodes. This would prevent the head exploding EVERY TIME A BULLET HITS IT because it would check for the last bullet on death. :D
Just a few suggestions.
SUPERFAST EDIT: Also, make Crowbar kills a gib no matter what. Everyone likes half-life and I miss that from HL1. XD