I still don't know why my download history was lost from the Market in the process of reformatting my SD card, but I was never able to get it recognize that I had downloaded anything... The following is the process that I went through to install the apps from the Market again. There is probably an easier way (and hopefully you will share how), but this is what I could figure out!
1. Fortunately for me Clockwork Recovery continued to be able to read the card even though nothing else could (Windows, Linux, the phone when booted, etc...) so I could restore my stock backup (that I had not saved anywhere else...).
2. Once I restored that backup, I formatted the card (in Windows, doing it from the phone didn't seem to do anything) and used Astro to make a backup of my apps to the SD card.
3. I loaded a new ROM (I don't recall which one at the moment).
4. I copied my stock backup to several other computers to make sure I still have that if the card ever dies completely.
5. Went to the Market to see if it recognized me and had my history. It didn't
6. Used Astro to install the apps from the SD card hoping they would then be recognized in the Market. They installed fine, but the Market still showed I had downloaded nothing.
7. I went to the phone settings to manage the applications to write down a list of what I had so I could re-download from the market.
8. While looking at the list I remembered that if I went to the applications properties I had the option to share the app. I used that option to send an email to myself for each app.
9. I loaded a new ROM to start fresh, again no history in the Market.
10. I went through my email and clicked the link in each message that I had sent myself in step #8. This took me to the Market and I downloaded and installed the apps from there.
Even though steps 8 and 10 took awhile, I think it was faster than manually searching for the apps again in the Market. I have also archived those emails so I don't have to start from scratch if this happens again. I have since loaded several ROMs and the Market seems to be working great.