I learned this method from another forum (can't remember where); it always works for me:
  • Exit all applications on the phone
  • Home > Settings > Applications > Manage Applications > All
  • Market: Clear Cache, Clear Data (OK)
  • Google Services Framework: Clear Cache, Clear Data (OK)
  • Reboot your phone
  • Open Market app and Accept the TOS
  • Market > Settings > Content filtering > Set level > Show all apps (OK)
  • Market > My Apps: no more missing apps, or false positives for updates
I've tested this many times with the new Market app on my AT&T phone in both stock GB and piCRUST. It always fixes the display of installed apps within the Market app itself. But the list of apps showing on the Market web site under My Account (https://market.android.com/account) may not be immediately updated with the results. Sometimes the Market web site will be updated later rather than sooner, or only partially rather than completely. But this local fix will usually affect the web listing to at least some degree.

(Space reserved for future rant on market web site lameness...)