How to get this quest
Once you have completed Fortress Of Wrath and obtained the Final Shield quest, talk to Mira in the Adventurer's guild about Richard's anchor.
Getting into the Maid Academy
The academy is the blue-roofed building on the eastern shore of the world map. You'll need to fight your way through the catacombs (see below) or enroll to be trained as a maid.
You can only enroll after defeating Lilim during What Lurks Within The Mountains. Note that Paulina will not gain regular experience when enrolled in the maid academy.
Gaining Maid Score
After enrolling in the academy, the next step is to enter the building where you will get your initial maid score. The initial score is computed this way:
Paulina's also has a maid score which starts at 0 and caps at 0.
The opportunities to gain maid score are:
Reaching 100 maid score will allow you to obtain the letter of recommendation from the maid at the desk. You will after that be able to end your enrollment or continue getting maid score for more rewards (1 magic thread for every 10 maid score beyond 100). Note that graduating fails the quest and makes you miss a total of 400 experience.
The Catacombs
Aura will need to fight her way through the catacombs if she wants to avoid maid training. Of all the lewd activities you can skip, maid training is one of the hardest. The monsters here are more difficult than anything Aura has faced yet. The guards will stop you from entering even the first entrance to the catacombs until you have enrolled as a maid and at least spoken with the trainer, so there's no escapaing wearing a maid dress. Progressing through the midpoint of the catacombs will require 60 Agility or a large number of bombs.
The catacombs run beneath the maid academy and can be entered from a variety of points, each of which takes you a little deeper into the catacombs:
The catacombs are filled with pollenfog, similarly to the fog Aura encountered during What Lurks Within The Mountains. To get rid of this fog, you need to purify all negative energy points contained in the academy's secret room.
Once you complete the catacombs and make it to the secret room, you'll need another 15 Bomb+ to proceed directly to Asmodeus's lair. Your alternative is to exit the secret room and sneak through the long hallway filled with guards.
After you've killed Asmodeus you will be unable to enter the catacombs except via the front garden entrance. Aura can lower a rope near this entrance to be able to access it later without the use of bombs. The catacombs have a few powerful bosses who drop rare material that you may want later.
Reaching Asmodeus
Asmodeus is on the academy's second floor. You can access the second floor either from the north wing or the secret room. Sneaking through the north wing requires either Shadowcloak II or 60 AGI. Going through the secret room requires to destroy an obstacle.
Once you reach Asmodeus, a battle occurs. A stronger version of Lilim will fight alongside Asmodeus. Note that both bosses will start with a MATK boost unless you purified the negative energy points contained in the secret room.
If fought on day 100 or after, Asmodeus has regained his full power and removing Aura's collar is the only realistic way to win; otherwise his stats are reduced massively, but can still be a challenge.
The fight has quite a few mechanics:
While Lilim is alive, she causes an unclearable blinding pollen storm, making attacks and martials unreliable. After Lilim is defeated, the pollen storm can be cleared with a wind spell.
Asmodeus has a special skill which negates the usual demonic Light weakness, and he resists Physical. He has one elemental weakness which changes each turn, and resists all other elements. It rotates from Fire -> Water -> Thunder -> Earth -> Wind, always in that order. He also can and will quickly remove the Defenses Broken debuff from himself.
In addition, he will occasionally use a special debuff 'Bondage Fibers'. The debuff reduces AGI and DEF and deals mild untyped damage each turn for 4 turns. Worse, when the debuff is present Asmodeus becomes able to cast 'Libidine' to drain energy from Aura; this deals additional Dark damage to Aura and grants Asmodeus five turns of 1000 HP/turn regeneration. If the debuff remains for a few turns Asmodeus will cast Voluptas, which causes Confusion and Paralysis along with +1 Corruption and +1 Orgasm.
Bondage Fibers can be removed using a special 'Break Bondage Fibers' martial skill, which costs 30 HP. However, the martial skill has a requirement of 15 ATK per remaining turn of the debuff (meaning 60 ATK to break out immediately). Buffs contribute towards the ATK requirement; for example the 25% buff from Heat Up I makes it possible to excape immediately with only 48 ATK. Note also that the AGI debuff from the bondage fibers may let Asmodeus cast Libidine first on the same turn that Aura breaks the fibers - in which case the debuff is removed but Asmodeus keeps the regeneration.
It is highly recommended to burst down Lilim first with bombs or magic, then focus on Asmodeus. Without extremely high damage, it is important to have enough ATK and AGI to remove Bondage Fibers immediately before Asmodeus can cast Libidine.
Defeating Asmodeus will lead you to immediately completing the quest. If Paulina's training didn't progress too much, she'll also turn back into Paul.