Unfortunately, "wiping" everything is sometimes the only way to solve certain problems. iPods can get "confused" after a while and need to be either "reinitialized" in MC or fully "restored" in iTunes. This means that you'll have to re-sync everything, but this is really the first step in troubleshooting since it's the most likely culprit -- i.e. it's not worth trying to troubleshoot this in other ways if you are not 100% sure that these processes don't solve the problem.
Most people try the MC "reinitialize" first since this won't reset all your iPod settings. After the reinitialize, do a sync. If the problem persists after this, try a full iPod "restore" in iTunes followed by a reinitialize in MC, and then another sync. I know it's a real pain to have to re-sync everything -- especially more than once -- but if a file on the iPod is corrupt, this is how you fix it.
Note that you can avoid the potential of having to do two full syncs by just jumping right to the full restore/reinitialize process first, but the restore will reset your iPod to it's original factory settings, so you'll have to set things up the way you like afterwards. I tend to try the re-initialize first since people have reported this as solving various issues. I have personally witnessed the full restore/reinitialize fix various iPod glitches in the past, particularly after certain MC upgrades make changes to iPod support.
If the full restore/reinitialize doesn't solve the problem, report it here and include the fact that you tried these processes. At this point you can start to do things like turn on logging in MC in order to help JR zero in on the problem.
When you say that wiping everything is not an option, is this because you have files on the iPod that are not on your system? If so, it's still possible to copy them from the iPod to the system before wiping everything out. You'll have to view the iPod in MC in order to browse and pull off the files that are not already on your system, after which you can re-tag them with the correct art. In the future, you should make sure to always have your full library of media on your system, and just use the iPod as a "temporary" viewer with the knowledge that it could be dropped, lost, stolen, or the files could become corrupt at some point.
Larry