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.