Finding IT job in Germany - all the challenges

Not having seen your application and knowing the companies you applied at, it is of course difficult to tell why you could have been rejected. Most probably, it is a combination of the reasons you mentioned and other you didn't think of yet.
Most (but not all) German employers are quite picky about the applications. After all, they are the fist impression of how you structure thoughts, present issues and convince others - and convince you must: That you are the best person for this job over all others.
All the advice you read is correct - also the seemingly contradicting ones: There isn't ONE application style, and different employers might prefer different styles. Therefore, it needs to be part of your research, before applying, to find out what kind of company it is and how best to present yourself to them. Sending the same CV and cover letter to all will fail - in Germany more so than elsewhere.
Of course it might also be that the companies shun the (travel) costs of inviting you for an interview. To prevent this, you could suggest a first screening by phone (or possibly video telephony - but then again, many companies dislike Skype) or arrange a trip on your own cost and tell them "I will be in your city from ... to ... for a private trip and that would be an excellent opportunity for a first meeting."
And, last not least, many jobs in your domain are being offshored to cheaper locations. Why should a company pay somebody from a poorer country German wages if they could hire a similar person at abroad for a fraction of it? You must tell them the answer to this question!

Thank you, beppi, for these insights.
You are probably right about different application styles being preferred differently by various companies, yet I don't understand one thing, among others: why (or better HOW) should the CV be different when applying to different companies? Shouldn't it be a kind of personal "job-diary", in a sense of a compilation of all your previous jobs (in the field), your skills and knowledge? Of course, you may omit details like if you worked as an actor in a theatre prior to starting a programmer career, when applying for an IT job, but otherwise I don't see a reason why (and how) should I change it from company to company, when applying to similar (or even SAME) kind of jobs? For the Bewerbung itself - ok, it's clear, but for the CV - I don't see how (and why) should it be changed...
Other suggestions - like offering meetings on my own cost - sound quite well. I will give your suggestions a thought.
Thanks for the advices!

The CV should, in a clear and concise way, show everything you have that is relevant to the job (or fits the style of the company) - and nothing more. That way you show that you understand the nature of the job and that you are able to concentrate on the essential.
It might absolutely make sense to mention a prior acting engagement (or even a hobby) when applying in a creative, open-minded organisation that values diversity - but the same will kick you out at a conservative, engineering-driven one, where you better focus on projects and achievements.
You should not lie in your CV, but you can emphasize important aspects and omit irrelevant others. An experienced HR manager will recognize a standard CV and see that you applied without doing your homework. (I personally often don't even read the cover letter, because all applicants write more or less the same nonsense about them being the perfect candidate.)
Maybe you should get a good book about how to write good job applications?

Ah, you're the one "on the other side" when it comes to job interviews?... ;-)
Ok, do you have any recommendations with respect to such books?
Are you in IT business as well?