The Soviets had never really tried to sovietize their occupation zone in Austria (although they certainly milked it economically [1]) as they did in Germany, and a freely elected all-Austrian government existed from 1945.
Given those facts, what stood in the way for so long of the obvious solution of a treaty guaranteeing a free and neutral Austria with all foreign troops withdrawn? Mainly, it was that the Soviets tried to use the Austrian issue to gain leverage on the larger issue of Germany. Once it became clear that this strategy was not working, that the Western Allies were determined to re-arm West Germany and admit it to NATO, the Soviets agreed to the Austrian State Treaty in 1955 (although Molotov opposed the idea to the end). After all, it was hardly in the Soviets' interest for western troops to be able to use western Austria as a link between NATO Italy and NATO West Germany. Moreover, the treaty might encourage neutralist sentiment in West Germany.
The treaty, incidentally, was also a good deal for the Soviets economically: "While the United Kingdom, the United States, and France relinquished to Austria all property rights and interests held or claimed by or on behalf of any of them in Austria as former German assets or war booty, the USSR, in addition to $1,250,000,000, which it took from the country during its ten years' occupation, obtained tangible additional payment for the restoration of Austrian freedom. This included $150,000,000 for the confiscated former 'German' enterprises which Austria had to buy back from the Administration of Soviet Property in Austria (Upravlenye Sovetskogo Imushchestva v Avstrii or USIA); $20,000,000 allegedly advanced to these enterprises by the USIA; $2,000,000 for the confiscated 'German' assets of the Danube Steam Shipping company, and 10,000,000 metric tons of crude oil as the price of Austrian oil fields and refineries which had been Soviet war booty." Encyclopedia Britannica (1957 edition), "Austria," p. 749. (The same article states that the division of Austria, including Vienna, into occupation zones, had "worked without difficulty.")
[1] Under the Potsdam agreement, Austria did not have to pay reparations, but the four Allied powers were granted a title to German external assets, which covered property in many cases forcibly acquired by the Germans in Austria. The Western Allies decided in 1946 to transfer the German assets in their zones to the trusteeship of the Austrian government; and in 1949 they agreed to relinquish their claims to the property altogether. The Soviets, by contrast, insisted on their claims.