So simply deleting an app from your iphone is not enough. If you delete an app by clicking on the “x” you would assume the app was gone being that the phone asks you if you would like to delete that app. I deleted 4 apps yesterday from my iPhone. I just plugged it in to sync as I wanted to get some new podcasts to listen to at the gym in a few mins. The first thing the iPhone does is reinstall those apps. It has done this to me before but I didn’t really pay attention, nor care at the time. It is rather frustrating though that you have to go into iTunes and remove the apps as well. Make sure that you delete them completely from your iTunes Applications library or they will be reinstalled back onto your iPhone. It seems that your iTunes Library takes precedence over what is on your iPhone. It does not yet sync as nicely as Mobile Me does.
These apps not going away reminded me of this video and song from my childhood.