Di solito i backup sono memorizzati in questa posizione:
~/Library/Application Support/MobileSync/Backup/
Basta saltare in TimeMachine o qualunque sia la soluzione di backup e ripristinare il contenuto di quella cartella.
L'inserimento in questi file è incostante e basato sulla versione di iTunes e sulle impostazioni di crittografia, possono essere capiti solo da iTunes. Non esiste un modo semplice per ottenere informazioni specifiche (come contatti o calendari) da questi file. Oltre al nome dei file ci sono numeri e lettere casuali, quindi buona fortuna a dare un senso a questo ...
Per quanto riguarda il primo dilemma, non capisco davvero cosa sia successo. iTunes non ha mai eliminato un backup, a meno che non l'avessi fatto manualmente nelle Preferenze. Vedi alcuni file di backup in Preferenze di iTunes > Dispositivi, in particolare quelli che risalgono prima dell'aggiornamento a iOS 5? Trovo molto strano che nel bel mezzo dell'aggiornamento decida di distruggere dati così importanti.
Hai un backup di Time Machine? Stavi abbonandoti a un servizio di sincronizzazione come MobileMe o Google, dove i tuoi contatti e altre cose del genere sarebbero ancora?
E come hai effettivamente eliminato i file di backup? Lo hai fatto manualmente o il sistema operativo ha chiesto il permesso di farlo?