I included my address(as a friend told me he had to to get it through), although this is normally not required if you have IBAN/BIC.
Yes - it turned out to got rejected because I did not specify my address detailed enough (only city and postal code). I was also under the impression that SEPA did not require a detailed recipient address. It is a bit strange because whenever I perform SEPA transactions, my online banking system does not even provide enough space to enter the whole address of the recipient but they always get through nevertheless.
Anyway - thank you all for your replies and special thanks to MagicalTux for sorting this out and re-issuing the payment so quickly!