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 world map. After arriving, you can only proceed further by enrolling. One the the characters in the lobby, Lord Claude, will allow you to do so, but you need to have dealt with Lilim during What Lurks Within The Mountains. Note that enrolling into the academy will make Paulina unable to gain experience over time as long as you didn't complete the quest.
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 got 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
There is an underground area accessible from two points in the academy. Traveling through this area is the only way to complete the quest without getting maid score. Take the following warning: the battle difficulty of this area is far greater than what you met before if you tackle this quest just after The Hand Of the King.
The catacombs are filled with pollenfog, similarly to the one met 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.
It is important to note that killing Asmodeus will cause you to lose access to the hole inside the maid academy proper, only the hole by the maid academy entrance will remain available. It is recommened to place the rope by this entrance before killing asmodeus, unless the alternate path has been bombed open.
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.