Do airlines change out the ELB batteries before the recommended date?
Yes. If the CVR / FDR goes to the workshop with the ULB still attached, the workshop is unlikely (depending on the financial situation of the airline)to release the unit with less than half life remaining.
e.g. the unit goes to W/Shop at 4 years, battery has 2 yrs remaining, battery replaced.
Replacement battery has been on the shelf for a while, only has 4 yrs remaining, more than half-life, within the w/shop release requirements. That gives 8 Yrs.
Perfectly reasonable situation.