Roughly 20% of the time now, the song or podcast currently playing on my iPhone 3GS will display some completely random album art from another title in my library of 9967 songs, 19 podcast subscriptions. Songs can have podcast covers and vice-versa.
Unlike the answer suggested by Why doesnt my iPod show album art?, when I cross-check the Artwork tags of my Mac's iTunes (anything from 8.x through 10.4), I can verify that the songs with mistaken artwork on-device have the correct artwork on-Mac and that songs without artwork on-Mac display the generic "no artwork" icon on-device.
I've had this problem almost as long as I've had my 3GS. In the past couple months, my wife has also reported this symptom with completely separate hardware/software (both her own Mac and iPhone 3GS, neither of which migrated any settings from my machine).
Correctly-configured artwork should show as intended on-device. How can I restore the expected behavior?