I just replaced the battery in my 30 GB 5th generation iPod. The decreased play time with the old battery wasn't a problem for me, but the increased internal resistance was. Combined with the higher internal resistance at low temperatures, it could cause a shutdown even if the battery was over half full and the temperature was well above freezing.
There are many choices, many different prices, and little information on what's actually good. After some research, I decided to buy a 580 mAh battery from richmondliu88 on eBay for $3.99.
It arrived in Canada in under 2 weeks. The battery was packed in plenty of bubble wrap, and it arrived with two blue plastic tools. The tools made it easy to open my iPod, and they weren't destroyed by the process. It was easier to open the iPod because of past openings, but nevertheless, it seemed like the tools were of above average quality.
I just measured the battery using Rockbox battery_bench. First, I charged it until current in the battery debug screen dropped to zero. For the test, I played Dark Side of the Moon in MP3 format, encoded with LAME using preset standard, with repeat all enabled and JPEG album art. I tested it using my typical listening conditions, with the EP-630 headphones, an inline volume control which raises resistance to 70Ω, the screen off, and hold on. I'm running the PP502x cache bug and ATA DMA test build, which is based on e362e34. The battery lasted an impressive 19 hours and 45 minutes.
eBay item currently shows a different looking battery. Note the paper on the back, which needs to be peeled back to uncover a sticky area for attaching the battery to the iPod back. It's a nice touch, although it was unnecessary for me because the glue that was already present on the iPod back was very sticky and hard to remove.