I was about to open a thread for this exact reason.
Updates are screwing all over the place. If I update them on my iPhone and I sync iTunes sometimes tells me that there are new updates ... so I re download and install the same updates.
Sometimes if I update my apps via iTunes then sync it to the iPhone the App Store on the iPhone will tell me there are updates, the exact ones I just updated before.
Most of the time if you click on them they state "Installed"
If you click again on the Updates part of the App Store app it seems to cycle through 3 stages; latest updates installed, updates before that installed and current state of apps ( ie if all the updates are installed it says its up to date ).
Im either thinking this is some kind of logging thing or a MAJOR bug?
Hope my findings help you guys as I am puzzled too.
P.s. please try to cycle the updates on the App Store app see if its the same for you!