I entered the Iron Throne tower via the sewer then sent Imoen to the top while hiding in shadows. On the fifth floor, I took the two scrolls from the desk in the back room, then charmed all the information out of Thaldorn about the Throne's plans and leaders, and learned that I should head to Candlekeep next.

At this point, I tried going back to the Flaming Fist to get my pat on the back from Scar. He wasn't there, inside or out.

Next, I tried looking for him at the Duchal Palace. He wasn't there either, and I couldn't get in - clicking on the gate produced the annoying "You must gather your party before venturing forth" message even though we were all standing right in front of it.

Is it not possible to complete this quest, even though I have the evidence, journal updates, etc? Must I kill all those guys on the fifth floor to proceed? It's not a big deal either way, I just thought it would be cool to stealth my way through it.

You don't go back to Scar. You need to go upstairs (Flaming Fist) and talk to Duke Eltan, who will teleport you back to Candlekeep.

Wait, there's an upstairs? How did I miss that... I definitely found the basement.

Yep, that was it. That staircase in the corner of the Flaming Fist is pretty easy to miss, but I should have remembered it after talking to the duke the first time.

Yeah, it is easy to miss, especially in vanilla BG1. Not to mention what a decrepit looking staircase it is for the headquarters of the Flaming Fist -- I missed it, too, the first time I played; maybe more than just the first time, as it was a long time ago. :)