After a few apps had updates come out that I didn't get notified about I began wondering what was wrong with my phone. After a few well placed friends pointed me to an official Google Market message board.
Market app 'my downloads' out of sync with installed apps preventing upgrade notification - Android Market Help
This thread has been growing fast, with reports coming in of more and more users with this issue.
It seems this problem is global, with users from France and the US reporting, possibly others.
If you are experienceing this issue, please report it on that board.