We still have a lot of "rule compliance costs", esp. when a company has employees, but you can hack this. In the worst case you just source this paper work out. The problem is more that Germany lost its startup-mentality. The last time we were a real startup country is 100 years ago.
In the times of the German Economic Miracle there must have been a great startup-mentality here. That has been roughly 50 years ago.
And i'll throw Karlsruhe into the pot. It's called the internet capital of Germany, has lots of companies (especially web companies) and one of the best universities for computer science (and other technical fields). Living costs are relativly low.
http://www.paulgraham.com/start.html
"[5] A friend who started a company in Germany told me they do care about the paperwork there, and that there's more of it. Which helps explain why there are not more startups in Germany."