So, an update on my repair. I was unsuccessful in trying to get a ML-621S/ZTN battery in place of the factory battery. I believe that due to the extremely small size of the battery, applying heat to solder it in ruins the cell (or I'm just not that great at soldering). I tried two different ML-621S/ZTN batteries and after soldering them in, and running the radio for a few hours, they only measured 1.2v or so. They should be about 3v.
Therefore I took an extreme hack approach that is ugly, but works great. I ordered an Adafruit CR2032 breakout board (about $2 bucks on eBay) and an LIR2032 rechargeable cell (same size as a CR2032, but rechargeable). The battery was also about $2 on eBay.
I slightly enlarged one of the speaker holes with a drill bit, and wired the breakout board directly to the solder pads where the factory battery would be soldered in. Then I used some rubber cement to glue the breakout board to the front of the radio. See the attached picture. Yes, it looks ghetto or techno-steampunk, depending on your perspective. But it works GREAT. And next time the battery dies in a few more years, I can just replace it in 10 seconds without opening the radio. Also note that in this position, it does not actually block the speaker, even though it covers holes. The speaker is pretty small and is actually only in the upper left hand quadrant of scanner as you look at it.
After you attach the breakout board and solder it in, and power the scanner on, you can use a voltage meter to check the + and - side of the breakout board. It should measure about 3.2 volts without a battery inserted. Upon inserting a battery (which came pretty much fully charged) I was able to power on/off the scanner endlessly without being annoyed with reprogramming the clock (of course after programming the clock once).
Ugly but it works and its a heck of a lot cheaper than sending it to Uniden or buying a new scanner and it facilitates quick and easy battery replacements in the future. Note also that you could mount the battery breakout board on the back of the scanner so you don't see it, but in my application it would interfere with my mobile mount setup.