The fix you suggested, if I recall it correctly, has these problems
1. You lose all the data associated with the app.
2. The next time an app is updated you have to repeat the fix. In other words, it doesn't solve the problem even at an app level.
I think I may have found something that works, and I think 2.1 has made it less painful. I'm not certain its a cure, but I have reason to believe it is.
1. Upgrade to iTunes 8 and iPhone 2.1
2. Sync iPhone so you have a backup (I make a zip of my backup directory and save it off just in case - see
http://tech.kateva.org/2008/08/iphone-backups-are-stored-in.html for details)
3. Restore iPhone to original state using the restore button on the info tab. This wipes the phone.
4. When the phone mounts iTunes will ask if you want to treat it as a new phone, or restore from backup.
5. Restore from backup. This doesn't restore everything -- but don't worry.
6. Sync (this will take a while if there's music involved).
When all is done everything should be in place. In the past the restores still left me with a lot of cleanup, but this time I only had to arrange a few icons. My passwords were restored.
Now, why do I think this will solve the problem?
When I did this iTunes said I had no updates. The App Store on the iPhone said I had 4 updates. I actually used the App Store to apply the updates -- a process that has NEVER worked in the past and has been trouble for many people. This time it smoothly applied the updates, and when it was done it said there were no more left.
BTW, I now think this might be a keychain/permissions problem on the iPhone's version of OS X.