If you make any changes to the gallery using the normal dialog (either before or after doing the find-and-replace), then the find-and-replace changes will be preserved.

I figured out why this happens: Parsoid has two "modes" for gallery editing, we can submit the modified page using either the wikitext markup for everything inside <gallery>, or the HTML markup similar to what we show in the editor (and in read mode). When both are included, the wikitext "wins", and Parsoid's output includes both. That means we have to explicitly get rid of the wikitext to make any changes. This happens in this function:

ve.ui.MWGalleryDialog.prototype.updateMwData = function ( mwData ) {
	...

	// Need to do this, otherwise mwData.body.extsrc will override all attribute changes
	mwData.body = {};

	...
};

But doing a find-and-replace doesn't call that code (it's part of the dialog for inserting/changing galleries).

There are two ways we could possibly fix this:

• Get rid of the wikitext whenever doing a find-and-replace affecting a gallery. I guess T110543 is kind of relevant here, galleries could have a special "replace handler" or something.
• Get rid of the wikitext when loading the page. This would be easy, but it would likely cause dirty diffs in existing galleries even when they're not changed.

This has been fixed by the work on T329662!