In the Smithmore Mines, the game kind of leads you on to think that the ground/ceiling are safe to touch, however in the areas where it pinches a bit, the ceiling/ground tiles actually become deadly. Took me a bit of messing around to figure out that's what was randomly killing me.
I've tested a few sections where the ceiling/floor change in height and the problem is consistent. Doesn't matter if you hit them from the side or top/bottom - they seem deadly all around.
[EDIT] Happens in the Cat Bug Hive as well. Probably safe to say it happens anywhere that the floor/ceiling changes.