I felt like playing this game last night, and surprisingly enough, I played it all the way through in one sitting. It's not that tough -- after getting used to the enemy patterns, it all comes down to getting your timing and positioning right. I would
NOT call it a puzzle game at all; it is an action/maze game, with the same type of enemy dodging and item collecting as
Cratermaze/Doraemon/Booby Kids. If the stages and enemies get a bit tough, all you have to do is kill lots of enemies so that the extra lives rack up. Batman is incredibly generous with extra lives, and it is this which makes the game quite easy, really. The final bosses also have very simple patterns, so if you show up to the Cathedral with enough power-ups, they'll all be pushovers. I found myself having fun in Batman, without even realizing why.
Anyway, I also took lots of screenshots of the great cinemas in Batman, so take a look near the bottom of this page to see them:
http://www.disgruntleddesigner.com/chrisc/gamesillust.html