Just a quick update. The office of Frank Schäffler (a member of the German parliament) forwarded me a letter from the German finance ministry dated last week, which says that Bitcoin is not VAT exempt according to §4. In Abs. 8 b UStG, confirming my previous worries. Their main argument is that BTC is not recognised as a legal tender in any country. Even though the letter does not explicitly say whether other exemptions apply, I suspect they don't. So be careful when trading BTC as a VAT registered company in Germany.
This is indeed bad news. However, there is hope. Let's have a quick look at what §4 Abs 8 b says:
b) die Umsätze und die Vermittlung der Umsätze von gesetzlichen Zahlungsmitteln. Das gilt nicht, wenn die Zahlungsmittel wegen ihres Metallgehalts oder ihres Sammlerwerts umgesetzt werden,
"Gesetzliche Zahlungsmittel" refers to official currencies. As long as there is no country that makes Bitcoin an officially accepted currency, this section does help Bitcoin being exempt from VAT.
However, there is another section just below (§4 Abs 8 d). It says:
die Umsätze und die Vermittlung der Umsätze im Einlagengeschäft, im Kontokorrentverkehr, im Zahlungs- und Überweisungsverkehr und das Inkasso von Handelspapieren,
This corresponds to Article 135 d of the VAT directive, which exempts the following from VAT:
transactions, including negotiation, concerning deposit and current accounts, payments, transfers, debts, cheques and other negotiable instruments, but excluding debt collection;
Here, it clearly says that payments and transfers ("Umsätze im Zahlungs- und Überweisungsverkehr") are exempt from VAT. The question now is: do Bitcoin transfers and Bitcoin payments qualify as payments and transfers in the sense of this directive?
My hope is that this is indeed the case. I'm Swiss and Switzerland has basically the same clause in its law. I know a VAT tax expert who will provide me with the official comment to the law, which hopefully contains further hints.