A code scanner will be run that examines the system calls and makes sure that it isn't using internal/undocumented APIs that may cause the app to fail when the operating system is updated.
And yes, this is done for every app and every update. Free and paid. Yes, it requires a crazy amount of manpower.
This is also something that introduces a human component to the review process - it is possible to get someone who misinterprets how the app is working or how a particular rule is applied to the review of the app and human mistakes can be made.
Friends have seen the same problem, with different bogus API violations reported.
Apple's made themselves the sole arbiter when it comes what software is allowed to run millions of people's phones, so I'd hope so!
Imagine the bureaucratic nightmare that would erupt from automating that process, and the businesses that will live and die based off of an automated filter deciding whether or not their products can be sold to users who want them.
Google is doing that right?
AS for margins, once you factor in Apple's high spending on R&D and engineering, their margins are fairly normal. Apple are financially successful because they sell high quantities and don't chase the extreme bottom of any market. Notice for example how they don't (currently) offer any mainstream external displays.