An interesting scenario. I thought deleting the app deleted everything, not only the app filesystem but NSUserDefaults, associated keychain items, etc. Does it matter whether you delete the app in iTunes or on the device?
Rather than ask what iTunes doesn't backup, start with what is does backup. See iTunes will back up the following information on this page for an extensive list.
Also read this if you use iCloud.