The iPhone Backup Extractor extracts data from iPhone backups. As such, so long as the last backup was taken before the data was deleted, it will recover your information automatically. However, if the data was deleted before your backup was taken, it makes sense that the backup won't contain your data.
Fortunately, Apple don't purge deleted data from their database files, so it is often possible to recover some deleted SMS, note and contact data. By extracting the SQLite databases from your backup in Expert mode, and opening them in Notepad, you should see fragments of any data that has been deleted.
This isn't the easiest way to recover data, and reassembling contact information isn't easy, but it's better than losing the data altogether! Registered users who need to do this can send us their SQLite databases and we can extract the textual information for them, although we cannot guarantee its legibility or use.