If you're going to offer a service like this, you want a few tiers of verification. You should have a lightning fast level 1 service that returns an automatic response. Perhaps level 2 would be a more computationally expensive automatic response. Level 3 might be human analysis, but the image would be just one of several shown on a screen at once. Level 4 would actually get a human's full attention for a few seconds. And Level 5 would be to handle strange cases, do CP reports and handle disputes.

Yes, such process could be perhaps most optimized, but the most problematic step is step 1.

Sure, it would be hard, there's some projects that might be able to help out however, e.g. https://github.com/pa7/nude.js. It's not an easy problem to solve but it's possible. You could also start the service with 2-5 of 1123581321's example or just 2-4 and wait to see what your customers request.