In my opinion, it is probable that you saw the Leechkirche on Rittergasse with a Teutonic Knights cross painted on the doors, instead of a garrison church of a hypothetical German army garrison in Graz during Nazi rule.
Graz in Austria was part of the Duchy of Styria in the Kingdom of Germany in the Holy Roman Empire until 1806, ...
There are churches in Germany which used to be associated with garrisons as their parish. Generally those buildings are regular churches these days.
Berlin (German link).
There are military chaplains (German link) in the German armed forces. Most are Catholic or Lutheran, there are talks of getting Jewish or Muslim personnel. These chaplains have ...