I found the area I think (I have a check mark next to the clue now) but I'm not sure how to get the prize. At first I thought that I must have simply not gotten the egg yet but I battled what at least felt like a zillion enemies after getting the check mark with no luck.

if it is localised in the third region you will found it on the ground, the dongeons will only be checked once you beat it

The egg is not a physical item, it does not show up anywhere but in the one battle log (or when you pick it up from the zone)

When the green check appears, it means that the prize listed on the left has been delivered directly to your inventory.

Thanks for the explanation!