I never understood how that flies by Apple's review. Aren't all code changes supposed to go through their review and thus OTA is effectively illegal?

Power on pluggable bundles. So you can change the business logic, but if you want to change any native dependency then you do need a new app binary which needs the same app store review process.