There are such a few amount of blunt melee damage, sharp melee damage, no weapon cards that searching for just the right one can take the entire deck and it really takes you out of the game if you are waiting for the keeper to find just the right card.

Are you also considering the "Melee Weapon" cards? Those are used with both Sharp and Blunt Melee Weapons.

I had to search for "No Weapon" a lot in our first game and

1. yeah, there need to be more combat cards, especially in a story where all monsters are of the same type
2. your keeper might as well speed up a little, take the whole combat deck and pick them faster. Maybe even turn the deck around and search from the BOTTOM of it. *Much* faster since s/he only has to skim the cards and works the same as it does by drawing cards.

One of the reasons an App would be awesome!

We've played 4 times now and for speed I always pick up the deck so I can just flip cards til the right one comes up. Saves a little (or a lot sometimes!) of time over drawing, looking, discarding...

I'm sure the inevitable expansions will all include a few more each time.