When I updated my software to U504 I had to again pair both my 40 and 52 remotes before they would work on my Living Room Hopper3. But the Family Room Hopper3 did not have any problem with my 40 and 52 remotes when I updated the software to U504.
This is totally speculation, so take it as you will. I'm extrapolating from how I know computers work. I think a given remote stores the variable for remote address in volatile memory. Thus, there has to be a constant flow of (small amounts) of power going to said memory, or it'll default back to a factory state. So if the CMOS battery is dead, the remote will lose all information that had been changed since it was first built, and it'll do that every time the batteries die/are changed. If I'm right, short of taking the thing apart and replacing the CMOS battery, or Dish replacing the remote, there's nothing that can be done about it.