The iOS Reverse Sync: Urban Legend or Real?
I am so sorry seeing your two questions about stolen data and property. Ugh.

I would recommend PhoneView to get the songs back (as well as all sorts of other structured data) - the free download works for a limited number of songs, contacts, etc... You pay to unlock the entire iPhone's worth of data once you are sure it's what you want for the job.

I have had good luck getting pictures, contacts and songs off an iPhone that iTunes insisted was corrupt and needed a restore. The OS on the phone needed a restore, but my data was luckily still fine and salvageable.

Lastly, you didn't ask, but I also really like CrashPlan which also has a free trial period for off-site backup of your data.