I thought I'd post here just to help anyone else trying to do this quest. We've been at Medusa for 14 days now. We've also haven't seen her in Beseiged. After several GM calls, one of our members got a reply saying that the NM was working as intended and that a requirement hadn't been met. No idea what the requirement is.