Base the company in Germany, problem solved. Here it is legal to reverse engineer and reimplement stuff, as long as you're doing it to obtain compatibility with other apps/platforms.
Stated in such a general way, this is not true. It's just the case that some contractual preventions of reverse engineering might be invalid. But the moment you distribute something, patent laws can become a big problem.
