"My Apps" in App Market only showing SOME past downloads after a reformat?
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.