How to find Beelzebub: Use your eyes and look for it. [/sarcasm]
I generally bring either Fly wings or the Teleport skill to abbey03 and warp around until I find something that looks like a Steel Chonchon. If you find that, it's Beelzebub. If you hear a buzzing noise, it's Beelzebub.
Note that you can also get Beelzebub out of Class Change, so another way is to use Abracadabra. Be warned that it's rare to get the
? skill, a 1/5 probability to get Class Change, and even then it's a random MVP that pops out(heck, you might even get Ghostring, Angeling, or Deviling). You also need a nonboss monster to change (I recommend using a Dead Branch).
