Housing market in Munich sucks. Going homeless is normal. Renting a dog house in Munich is out of the reach for middle class.
One aspect (besides having a substantial salary) is to be quick to respond to new ads. Typically, if you respond to an ad later than 30 minutes from publishing it, you will not get any response.
To stand a better chance in this version of hell, you need to automate. Here is a script which helped me to find roof.
This script polls several websites, and sends you an e-mail as new ads appear. The code is crap, who cares.