The Fürstenhof has only 92 rooms, so it can fill up sometimes - I barely got in a couple of years ago, as an IOC delegation studying Leipzig's (ultimately unsuccessful) bid for the 2012 Olympics had taken up most of the hotel.

But I've gotten rooms there in the Eur. 118-140 range over the last couple of years. Staying with Starwood, there's also the Westin (very close by, and even closer to the Hbf), which now has the Heavenly Beds and is perfectly fine (I stayed there on my last trip as the Fürstenhof was sold out). Good views, since the rooms occupy floors 15-27 (IIRC) of the building that houses the hotel.