Go to Settings->Store and check your automatic downloads. If you have an iPad it could be re-downloading an app from that as I downloaded a phone and it went onto my iPad when I went to delete it off my phone then iPad, I noticed later on my phone had the app again. But that was with iOS 4.3 I believe.
I am having the same problem, delete an app from my phone and when I sync to iTunes it gets put back on there. I am not seeing any check boxes for that yet, hopefully Apple has a fix coming.