Formal education (university degree) is required to get a work visa pretty much everywhere. I think this is why you get rejected all the time.
However, a friend got his visa for Germany turned down because he didn't have a degree.
If you went to Austria instead (of Germany), you probbably would have needed a notarially certified copy of your diiploma (there is a true story behind this sarcastic remark). ;-)