The behavior of block validation works by comparing the output of what the editor would save as a block against what is actually saved in post content. Therefore, if the generated output of a block ever changes, all previously saved blocks would then be considered invalid.

The options here are:

• Blocks must never change their generated output
• Accept that validation will flag the blocks as invalid. The behavior of "Overwrite" may or may not allow the block to remain intact, depending on the changes and implementation of block attributes (i.e. those sourced from content may be more subject to breakage).
• Implement block versioning, so that previous versions can remain unaffected by the new markup. Presumably each of these implementations would need to be registered, but only the latest version offered for new blocks.
• Implement block migrations: Similar to versioning, but assuming a block implementer understands a change they're making, they could explicitly define a path for migrating attributes of the previous version to the now-updated implementation