I'm among those who have never had my apps come back after a wipe, in spite of having all sync methods active. I haven't paid attention to wifi settings. I'll try the nandroid data restore when I update next...
In any case, it's really whittled me down to the apps I actually use. ;)
Gmail does backup and auto redownload all market installed apps to your phone upon first sign in as long as you have BACKUPMYSETTINGS enabled. The problem is getting PETES rom to prompt sign in.
Next time you flash Petes Nandroid IF you wiped data first ( I always wipe when changing roms) make sure you dont flash the Nandroid DATA from PETES rom and it will prompt you to sign in on first boot OR if you didnt wipe data then dont restore Nadroid DATA from Petes rom and all your stuff will still be there.
I have used most of the way you all have described, and can add only one sort of new way. When you go into Market, you can hit the menu on the phone, then downloaded apps, and then "force" the install.
One little trick that I have found that really helps me when trying anything new on the phone, be it nandroids, update, apps, etc. is to use windows explorer or 7Zip to explore every file I download. You can cruise the entire file, check out what it is gonna write and compare this to what you are expecting from the file. You can even use Notepad++ ( a free windows program) and even open things like the phone.prop file. I like to peek at all of these. Damn, there is CorpCal again.........:)