The new permalink structure is only saved when WP_Rewrite::flush_rules() is called. Because this is an expensive operation (calculating the new rules and saving them to the database), you should not do it on every init call, but only when you change the structure. The custom post type however must be registered at every init call, since it is saved in a PHP array in memory, not in the database (which is why it forgot the custom post when you switched themes: the permalink structure still existed but referred to a custom post type that was not loaded, giving an error).
