Very bureaucratically burdensome, considering the ROC's typical protocol (medical test is super simple). There is more to the story than meets the eye. I would imagine there will be many exemptions. That said, something has indeed changed but it might not be such a big deal after all.
However, FBI checks are usual business for work visas in South Korea.
Japan's work visa is super simple (no medical test needed, either). But you have to leave the country to get a visa (then come back). Just go to SK.