I've nuked my phone and got a replacement, If they don't show up, make sure your using the same live account, then go to the marketplace, find the app that you paid for, then select buy, it will check and prompt you "you already paid for this app, do you want to reinstall it ?" then just say yes.
Most cases, if they are small apps, they will just automaticly install...
If your like me, who has about 15 apps and games from the marketplace, just make yourself a small list, so you don't forget one.
Edit: If your phone is unlocked, there is an app on XDA that will backup your 3rd party app settings. Yes, it will move your save games from xbox/non-xbox live to a new phone (found this to annoying after a few times, to get back to the same level)
Aka, backup, Nuke/replace your phone, unlock new phone, install the games/apps from the marketplace (or where ever), restore backup..back to where you were...
http://forum.xda-developers.com/show....php?t=1223619