We're all over Europe and the U.S. It was pretty painless. Our business does not rely on the ignorance of users or the abuse of their privacy. What "army of lawyers" did you have and why was the spirit of the law not enough? We had several different business units get through compliance without any problems.
This isn't a hard thing to address at the end of the day (so long as your entire business doesn't depend on it). I just can't help but feel a few ways A) You didn't understand what the law says B) what your lawyers were actually worried about or C) this story is just made up.
What specifically were the discrepancies in the interpretation of the law between various countries that caused two "top" tier law firms to be unable to come to a clean consensus?