I used to be able to go to "My Apps" and view all my past apps. Now that I've done a reformat, though, I only see a SMALL subset of the apps I've downloaded before. I thought it was supposed to show all my past downloads?
Its been my experience that only paid apps remain in your my apps list after data is erased from your phone. I believe that the list of downloaded free apps is stores in the phones memory so its lost when you wipe it. This is the benefit of services like appbrain.
Edit: As thunsaker points out, if you use Google's Android Backup Service and you have a 2.2 or later device it will save the list of your downloaded app (among other things) and restore that to the Market after a restore.
It will only show apps you've purchased from the Market (at least, that's the experience I've had) besides the ones currently installed on your device. I recommend Titanium Backup (requires root) for backing up all your apps.
Is this the first time that you've opened the Market since your reformat?
My experience both with moving from an old phone to a new one and after a factory reset, was that once I'd added my primary account onto the phone, the first time that I opened Market and went straight to My Apps, I saw every app that I had on my previous device both paid, and free in the list (the free ones showed in the list as "Free" rather than the normal "Installed").
If I then came out of Market, the next time that I opened Market it just showed me my paid apps plus the apps that had actually been installed on this phone since the wipe, it had now 'forgotten' my previously installed apps and I've lost the chance to easily find and reinstall them.