"Other" is all the stuff that keeps your device working; the OS, pre-installed apps (Safari.app, Music.app, etc), settings and database files, contacts, and a lot of other stuff. For a non-jailbroken device, it should be from 400 MB to maybe about 700 MB. Considering you have an iPod Touch, it should be much closer to the 400 MB end (and it is). There is nothing you should do about this. Everything is working normally here, but if you really want to get a few MBs back, you can (and as you said, have) do a full restore and build the device back up from a fresh start.
Now, the data storage industry has always been a tad shady. You never feel like you get what is advertised. You can go out and buy an 8 GB flash drive, but when you come home and plug it in, it might only show up as maybe 7.3 GB. This is for multiple reasons from one guy using 1024 as the number of bytes in a kilobyte and another guy using 1000, or from system files the drive requires in order to work. You rarely get exactly what is advertised (or at least in my personal experience). Apple does this as well, so while you bought an "8 GB" model, you really only have 6 GB that you can actually use. That missing 2 GB goes to various things around the device, and an amount of it is probably generated from a 1000 to 1024 conversion. I'm starting to feel like a storage device conspiracy theorist here, so I'll cut it short and just tell you that in the future, if you need a device to hold 8 GB, get one that advertises it holds 16 GB. Better to err on the side of caution and spend a little extra than to err on the side of faith and get screwed over.
tl;dr
"Other" is always going to be there, and if you keep having to delete your old songs, you should probably just get a new iPod.