I'm loath to give them up, too, because damnit, that effect is useful so often. Buuuut when it isn't useful it's a dead card and when I play against members of the newer playgroup, dead cards will cost you games a little more frequently.
Overkill is a deck that I made in the "modern" era of my deckbuilding, which means that I recognized that it was a combo deck and anything that didn't enhance the combo needed to be cut. Therefore, no Naturalize.
Which is a problem when you play against a Stasis/Kismet deck. I didn't have the disruption to get out from under the lock, which is what happens when there are no Naturalize effects and Stasis comes out on turn 3. Show and Tell doesn't really help because even if I reveal an Emrakul, if Jason reveals Kismet...well, my creature is tapped and useless.
The question is: do I really need to address that?
The answer, unfortunately, might be 'maybe'. Matt also has a Stasis deck, one that I've beaten because I had answers to enchantments and he didn't have answers to that. Buuuuut.
Do I need them? Or do I just accept that this is the kind of matchup where I have a disadvantage. I ask this question because I know there is no way to make one deck be good in all situations. Maybe I should go even further: perhaps this is just a card that has my deck's Achilles Heel.
Now, if that card made up a broad percentage of my field-or even of the Legacy metagame-I would definitely feel compelled to tweak Overkill in order to defeat this particular angle of attack. However, on the curve, how many decks do I deal with that come at me this way? That's the real question.
I still think it's worth looking at some spells that are expensive-maybe one or two?-but perhaps it would be better to look at cards to help speed it up that were cheap.
Also, another copy of Show and Tell probably wouldn't suck.