I entered the Flaming Fist Headquarters, talked to Scar although I didn't complete any quests yet, and I told him I haven't found anything yet, but I'd like to keep searching. Then he left. Where'd he go to? I'm assuming the barracks, but I never could figure out where the Flaming Fist Barracks were (which also means I've never managed to receive my award after completing his last task).

The Flaming Fist HQ / Barracks are the same building. Provided you didn't tell Scar that you were more interested in pursuing Duke Eltan's quests, Scar should always be either in the first room of the FF building, or right outside the front door.