Did you try different weapons, or weapon types?
Is your current weapon broken, and needs to be repaired? (though a missing sword should be visible with your character in that case)
Try entering the battlefield, and see if you have the same problem against different opponents.
I don't think there is a curse or spell effect that can cause a no damage message...
What is your agility? A low agility would cause you to miss more often, but IIRC that would give a missed message, rather than no damage.