This thread seems like a Feature Request to me, so my response will be feature oriented.
Perhaps out of sync replays might not be the best thing actually. I certainly wouldn't want my old replay completely ruined because the BPM was changed. I also wouldn't want the scores wiped. Perhaps there would be a way that wouldn't affect existing saved replays. I think it might be worth including such a feature sometime in the distant future.
I could be wrong, but aren't the replays using the actual beatmap's object data? If you save a local replay and then change the where the objects are in the song, will that not affect how the objects appear in the replay? I haven't tested this, and plan to when I am in a position to test. If this is the case, wouldn't this make replays potentially unstable, and could be changed regardless if the user saved the replay. If this is not the case, then that means object data is saved on a per replay level. I don't see it being too difficult to add code that decides whether to overwrite or keep existing replay object data.
My Idea
A map that has BPM updated creates a replay file that goes in the beatmap folder or whereever it needs to go. Upon map update, it will inform the users that BPM has changed, and that old replays will need to use replay file to stay in sync. Use whatever method works best to distribute said replay file. Old replay formats will need to use the replay file, while newer recorded replays will not require the replay file. This could probably be done with the design of a shiny new replay format entirely or just a modified one that allows this.
The replay file will in no way affect score submission and is only used for older already processed replays.
A lot of text trying to say: Changes to replay data should be handled in a stable way, if we are going to prevent score wiping.