We are running NextGEN Gallery 1.6.2. For some reason, something about our configuration has resulted in a scenario wherein whenever we view the active gallery, edit the active gallery (e.g., changing a caption), reorder images in the active gallery, or upload an image to the active gallery, we see that rewrite_rules in wp_option gets written without the rules from the RewriteRules function in lib/rewrite.php.
The workaround is easy: visit Settings->Permalinks and click Save.
Unfortunately, if anyone with edit access to the site messes with a gallery and doesn't remember to save Permalinks afterward, we're left with a gallery full of 404s.
I've isolated the what but I can't translate that into why yet. It seems like something about editing the gallery is resulting in a reset of wp_rewrite->rules without the merged ruleset from RewriteRules, but how could that happen?