Sounds like either that other battery was bad or something is draining it. You do not need to register batteries on this car. The fact that he insists on that suggests that you need to go elsewhere.

I don't know about a recall. Also I've never had to reprogram my keys after disconnecting or replacing my battery.

__________________
03 3.0i mt
89 325is