that's a harsh place yes, but the key here is to admit that in EK you sometimes don't clean dungeons... try to find what you've come to find, grab and run away
I take it, your gossip didn't provide an exact location? then try luck, on the rooms on the dungeon corners. Avoid the mess hall to the north, and avoid the center area with the orc king and the elites. Go through the south route and hope you find it. If not, go back to Kingsbridge or NG inn and gossip some more...