While you can't normally battle it this early, running to the wall would provoke it, allowing it to be fought. This allows a level 28 Denjuu to recruited very early.
Btw, using escape from the first village early trick, you can fight this over and over BEFORE getting your first denjuu, and even to the point of evolving it. The game doesn't seem to break down if this happens, so I guess this can be used to grind.
This NPC located in Map 108 (address 3004F90 for Speed version) appears to be impossible to fight. Entering from the stairs, above entrance, and the right cause it to not appear, while entering from a different part of the room causes it to appear. If anyone can actually get this to fight you, please post how.
There probably be more, but I'm stuck in Map 108 because the place is confusing as hell. :/
I'm not surprised about being able to encounter the first one, but not encountering the second seems like a weird oversight. Also Blaziken made a labeled map of that dungeon, because yeah it is a HUGE pain in the ass -