If anyone else is interested – as we’ve figured out, the problem was the high number of users on the site (more than 100,000). Our plugin loads all users on the rule’s settings page (for the “Users” condition), so it required too many server resources to load all of them. To solve this, we’ve added a new option to our plugin in v2.6.0. Now you can disable the unnecessary conditions (e.g., “Users”) with the new “Disabled conditions” option in “WooCommerce > Settings > Order Status Rules > Advanced”.
P.S. In the next plugin version, we will use AJAX for the rule’s settings pages so that it can work with a high number of options as well. I will post about it here as soon as it’s ready.