If the same message appears when iTunes is not running, the error is probably coming from the OS X system, not from iTunes. Here's what I would try, since doing a Restore in iTunes does not resolve the corruption issue... Quit iTunes if running. Run Disk Utility and select the iPod in the Disk Utility sidebar. If there is a volume indented below the iPod device, make sure you select the device, not the volume. Use the Erase command on the iPod (to reformat it). If your OS X is El Capitan (current OS X release), in the setup window for Disk Utility Erase, set Scheme to Apple Partition Map. Set Format to OS X Extended (Journaled). Name doe not matter. Click Erase. If you are using an older release of OS X, Disk Utility looks different; please post back.
After the Erase completes, the iPod's onboard software is no longer present, so you still need to do a Restore in iTunes. Quit Disk Utility and run iTunes; whether you are prompted or not, do a Restore on the iPod. After Restore completes, before loading any content on the iPod, see if the "corruption" message still happens (or not) when you disconnect and reconnect the iPod.