Nobody ever bothered to post this information, so I guess I'll do it. This needs to be posted. There is no benefit blindly shooting random spaces, when you should be having fun shooting enemies instead!
I spent a few minutes watching a longplay. I'm adding to the prior locations, and adding time stamps where the keys appear in the video. Hopefully this makes the game more accessible to everyone. It's pretty fun!
Stage 1: in the Tower level, on the top floor next to a step (5:20)
Stage 2: in the bridge level, on the red house (13:30)
Stage 3: in the big stalagmite level, on one of the wooden posts (17:50)
Stage 4: the first level with the tents, shoot above a red lamp-post with the grenades (26:30)
Stage 5: no key, just go through the castle and fight the final boss