In my town there is a place called "All Batteries". That's all they sell, batteries... the small-ones, weird-ones, and all of the normal ones.
I think they have on hand (they have a bazillion different batteries on the shelves), or can get, damned near any size or type of battery smaller than a lead-acid car battery... they might even do those as well.
I pulled a special battery, one of those damned welded-terminal types, out of my infrared headphones. I handed it to the guy and grunted. He said, hmmm... oh yeah, right over here. He gave me a duplicate.
I believe they have an outlet on E-Bay as well.