Erratic battery percentage behavior
I'm a n00b so can't reply to your comment, but can hopefully give some more details in this answer. 

Yes, the battery on the 4th gen touch (assuming that's the correct model) is soldered to the board. It would be interesting to know what Target did, as Apple don't do actual repairs on iPods - it would have been replaced like-for-like under their warranty. The fact that you're having the same issue persisting after the battery was replaced, and you've ruled out software by restoring would obviously suggest something else as you mentioned. There's not much in the way of diagnosis avaliable for these but I'd guess that it's likely to be an issue with the power management IC on the board. 

If you're experienced with BGA work, this could probably be replaced, but it would be easier to replace the board if you can get hold of one, or to be honest just replacing the iPod in this case I think. Depending on the storage size, an out of warranty swap from Apple is maybe around $100 if you're in the US (90 day warranty), or they should give you around 15% off a new one in-store if you give it to them for recycling and buy a new one. Lastly, you could of course punt it on eBay or the like and get a new one.

Hope that's of some help.