Thanks to Twitter users @gattermann and @sjbuchanan007, I now know the cause, and the fix.
It turns out there are two versions of iTunes 9.1.1, as seen in the About box: 9.1.1 (11) and 9.1.1 (12). If you have (11), you want to get (12) from Apple's iTunes page, as it fixes the re-sync problem.
In reality, (12) fixes a different problem, which was probably the cause of my sync problem: in (11), the Modification Date on a song changes every time you play it. Version (12) no longer changes this field when merely playing a song.
For some reason, Apple did not push version (12) out to those of us "lucky" enough to get (11) via Software Update. So check your iTunes' About box, and if you see 9.1.1 (11), you'll want to go get the newest version yourself.

