I think it has more to do with age than to do with origin. When I was looking for a place in the UK after getting my first job and earning decent money I was straight up told by an agency that many landlords wouldn't even consider me because I was "too young to rent a house", even though I had the money for it. Age discrimination is perfectly legal everywhere(apart from job interviews maybe) - think car insurance - so it's very easily used as an excuse for everything. I also think that's wrong.
That was the case for me as well, back when I moved to Munich in 2012. It also helps if you speak at least some German(I didn't), and send emails in German(just ask some colleague or friend to fill it for you). Also, in the end(it took me roughly 3 months to find apartment) I just had a stack of papers which basically would tell everything about me. I dunno if it helps, but I have heard Germans like bureaucracy.
> Age discrimination is perfectly legal everywhere
It's protected alongside the statuses of disability, gender reassignment, marriage and civil partnership, race, religion or belief, sex, and sexual orientation, to more-or-less the same extent in theory.
There are, however, glaring exceptions when it comes to housing (due to how this protection intersects with property rights), as housing agency industry groups, housing charities, and various other charities explain across the Internet.
I think the most glaring omission is car insurance - if you enquire about insurance you will be straight up told that because you are under 25, the premium is going to be 4x of what it would be normally. No-one bats an eyelid at that - statistics prove that young drivers crash more, so it's all fine, right??
Funnily enough, statistically men crash more than women too - but it's illegal to charge men more, because that would be gender discrimination. It's also illegal to charge someone more for insurance because they are black, christian, or a vegetarian - regardless of how many accidents members of those groups get into. And yet if you are 24, have been driving more than 6 years without an accident, you will still pay more than someone who is 25 and has passed their exam last week. If that is not discrimination then I have absolutely no idea what is.
Funnily enough, statistically men crash more than women too - but it's illegal to charge men more, because that would be gender discrimination.
In the EU this became illegal recently. It also applied to women, who live longer than men, so were being charged higher life assurance. It just shows how anti-sexism laws can, and do, benefit men.