I'm with NORCAL, recycling batteries shoudn't be a problem with all the metal recycling going on. Many places that sell car & truck batteries take back the old ones, you should be able to find a battery seller that would take a few off your hands.

You might consider contacting the manufacturer of the lights to get replacement lamps. i know that this will be the most expensive route, but if the link posted above doesn't help you, it might be the only way.

Few things are harder to put up with than the annoyance of a good example.