When I exchanged, all my paid apps came back, and most of the free ones did too. Before the switch though I downloaded APLIST from the market. It generates a text file with every app you have and saves it to your sdcard. So I just went through and looked up the ones that didn't come back on their own.