I found a new shop today looking around, and asking opinions. European Specialty Motors. I didn't know they were there until I passed today, so I dropped in on the guy and asked him a few things. He knew everything that was wrong with it... the belts, and the alternator bushing being worn, something I hadn't noted (nor had the other shop, their solution was tighten the belts, which I'm told with worn bushings, will chew the shit out of my alternator belt).
I also found out they'd been working on my car with a 320i Haynes manual... you know, for the '75-'83 E21? I'm not impressed.
The fellow at Euro Specialty laughed at that, and told me that if they needed a Haynes manual to work on my car, they shouldn't be working on it in the first place. (As he said this, he had an E30, an E36, and an E39 up on lifts in the service bays) I tend to believe him.
EDIT: Oh, and by the way, according to the original shop, the belts are indeed installed correctly.