Can you make iTunes forget a device?
Reset the SyncServices folder. Not sure why I didn't think of this earlier.

In short:

/System/Library/Frameworks/SyncServices.framework/Versions/A/Resources/resetsync.pl full


Apple has some other tricks to try if you're on an OS prior to Mountain Lion, but it looks like this should work for Leopard through Mountain Lion.

You can confirm by comparing output of

grep -ir "device" ~/Library/Application\ Support/SyncServices


before and after resetting the SyncServices folder. You should see some lines about your device prior and no lines about it after.