I may be wrong, but if they have a presence in the UK they most likely do not need a presence in Germany. Through EU agreements, Germans are allowed to work legally in the UK.
They are allowed to live, work, and study in the UK without any significant restriction, and the tax issue would be a non-issue if they were domiciled in the UK. The reason it's interesting and complicated is because they're apparently living and working in Germany as an employee, without FogCreek having a German entity. They wouldn't be subject to British taxes and there's no German business entity to register with the German tax office.
A UK company (or a company of any jurisdiction) can establish a subsidiary in another EU state, in much the same way you could register a NY-incorporated company as a foreign company in CA, but this doesn't appear to be what's happened in this case.
