Rewrite rules are cached, and that is the whole problem

The rewrite rules are computed once and stored in an option, so a newly registered post type or endpoint returns 404 until something regenerates them — and the thing that regenerates them is expensive enough that it must not run on every request.

add_action( 'init', function () {
    if ( get_option( 'shop_rewrites' ) !== SHOP_VERSION ) {
        flush_rewrite_rules( false );          // false: do not rewrite .htaccess
        update_option( 'shop_rewrites', SHOP_VERSION );
    }
}, 99 );

Priority 99 so every post type and rule has been registered by the time it runs. The version gate turns it into once per deploy. flush_rewrite_rules( true ) also writes .htaccess, which does nothing on nginx and requires the file to be writable — a permission that should not exist in production.