This quest is no longer required for access to The Poets Palace. However, it is still required if you wish to obtain the access quest for The Pedestal of Sky from the Djinn Master inside Poets Palace.
The locations for the pillow, mat, eggs, and chalice are random spawns in a specific area. See the talk page for a detailed list of possible spawns and photos.
Go to Maj'Dul and search for a red pillow that can spawn under any merchant tent.
Possible locations: ( 61, 140, -70 ) or ( -67, 149, -137 ) or (53, 139, 46) or (-176, 177, -93)
Trackable as "a red pillow"
Go to The Great Bonsai in the Pillars of Flame and search for a harvestable mat. ( 149, -189, -1623 ) Copy/waypoint 149, -189, -1623 or ( 308, -167, -1663 )
Go to The Seer Stone in the Pillars of Flame and search for harvestable eggs. ( 24, -45, -400 ) Copy/waypoint 23.83, -45.14, -399.69
If using a land mount, take the ramp at ( -43, -75, -622 ) Copy/waypoint -43, -75, -622 or ( -20, -93, -253 ) Copy/waypoint -20, -93, -253 in order to climb up to the cyclops area and then cross the path at ( -80, -46, -396 ) Copy/waypoint -80, -46, -396.
The eggs can even spawn on the ramps outside the immediate Seer Stone area.
Spawns in random locations throughout The Living Tombs (confirmed at -451, 23, 344 ). It tends to spawn on top of towers an on ledges. Also spawns at -191, 33, 281 on top of a building in the left corner, up the oily wall at -438, 0, 356 or at -377.33, 26.46, 496.16 , at -193, 33.59, 282.70 in the Statue Court, at -432, 22, 359 up the first wall of Residence Court on a ledge and on a ledge in Residence Court at -43.24, 22.35, 360.38 .
NOTE: In order to climb the oily wall you must complete the quest: A Slippery Situation.