I register custom post type on init action and the validate which I’m
writing about is set to register_setting inside admin_init action.
This is the key to your issue. You’re registering the custom post type, and presumably you’re setting up the rewrite rules in that registration.
When you call flush_rewrite_rules(), the rules are rebuilt right then, at that time. So, in your validation function, you have not saved the new setting for your rewrite rules yet, nor have you updated the custom post type registration with the new rule.
Note: A sanitization/validation function callback added using register_setting runs before settings are saved to the database, not after.
Basically, you need to handle the change better. You can do this in the validation function, but you may need to modify the already registered CPT first. Basically, register it again with the changes. Then, when you flush the rewrite rules, it should rebuild them correctly, with your modifications.
The reason this works for you on the second attempt is because of the way you’re saving and flushing. You flush the first time, but nothing changes in the rewrite rules. Then, your option gets saved. On the next load, the CPT is registered with your new information, so your new rule is there, but you haven’t flushed yet. Saving again causes a second flush, and now your rule takes effect.