PlugStore (via TMO) is no offering a £75 iPod battery replacement service which promises quick turnaround:
You send us your iPod and we will replace the battery with a new one and send it back to you 24 hours later via registered post. It is as simple as that.
The service is currently only available for Gen 1 & 2 iPods (those with a FireWire port on top.)
More info...