I've run into that a few times with my Titan. It took me awhile but I think I finally figured out the fix. It's pretty complex. Ready? Reboot your phone.
Seriously, that's it. The times I've run into the bug, I reboot and go back into the Marketplace. Even if the live tile hasn't updated, all your updates show up again. In every case the missing updates were ones that had showed up at some point in the past but apparently never installed.
Yeah, the marketplace app and functionality of WP is kinda spotty. It won't tell you that there are updates sometimes unless you force it. Needs a bit of work. Maybe 7.8 and 8 will fix the problems.