Yeh, banks nowadays are very sensitive to all businesses related to high-risk activities for AML purposes. But if a business/service is really legit, then I would suggest a fundamentally different solution. If I was you, first of all, I would find a bank, who will look deeply into your situation. You would have to visit the bank personally and explain your business model (without revealing any confidential information) and then if they approve you, this bank will be trustworthy, it would never stop any transactions. In other words, I would find a bank that wants to know its customers personally and more deeply instead of︀ going through the road of formalities.
As far as the company itself is concerned, at︁ first you have to look at tax issues - how and from whom you pay︂ taxes in your country, what kind of resident you are and so on. And then︃ evaluate, whether it's offshore or just a simple company in Europe etc.