I don't have a great answer - but this is fairly serious so I'm going to start an answer and hope someone else edits or answers if they can spot something I haven't.
On the computer, the only "red flag" would be if you wiped the phone of all content and settings, named it exactly the same name as it was before (which could be iPhone) and then backed up again and overwrote the backup with the actual data. iTunes tries hard to prevent this and spawn off a date-protected backup when it detects this, but I've seen this check fail and people lose backups from time to time. The remedy here is to restore the PC from a backup that has whatever MobileSync folder is the most recent.
On iCloud - you also shouldn't be able to overwrite a "full" backup with an empty one. Also, iCloud explicitly keeps several versions of the backups going back in roughly day intervals. It also normally stores backups for different devices without collisions or overwriting another backup.
The good news on iCloud is you can always get help from Apple at http://www.apple.com/support/icloud/ and from retail stores. New devices or ones covered by Apple Care also have phone or web support in most countries. All new Apple products have a 90 day window of set up help. Hopefully one of these can step in and assist. Not only does Apple get a data point where their tools let you down (and exactly what circumstances this happened) - they also see many people in this situation and will hopefully waste a minimum of your time getting this sorted.
I was searching for information on this myself because I needed to back up my email data from the device before doing a restore (it's just shameful that Apple doesn't consider your email messages to be important enough to include in its backups). The following information is valid for IOS 6, I hope it applies to your situation with IOS 3 as well. On IOS 6 at least, you won't need to mess around with SQlite or anything, it's all plain text.
You need access to the filesystem on the device. There are various PC and Mac apps that will browse the files on the device -- Ifunbox is one that claims to allow access to the filesystem without jailbreaking.
Instructions for jailbreaking your specific device (if it turns out you need it) can be found at http://stateofjailbreak.com/guide/iphone-3gs/3-1-2/.
The emails are stored in User/Library/Mail (that's a symlink, the actual path seems to be var/mobile/library/mail). Just copy the whole thing to your laptop.
Inside there, you'll find directories named after each email account set up on the device. There's a pretty self-explanatory folder structure within each account folder. Once you drill down, the emails themselves are stored in individual plaintext *.emlx files, complete with all headers and uuencoded attachments (there's also sometimes an "attachments" folder which has the extracted version of the attachments). On a PC, you'll want to rename them to *.eml files, and then you'll be able to import them into various email programs like Thunderbird or Outlook; with some you'll need a utility, with others the import function is built in.
I haven't gotten far enough to determine if copying a backup of these folders onto a device restored from itunes backup will restore your archive of emails or not. Did I mention how annoying it is that Apple doesn't think your offline emails are worth saving when you do a backup of your device?
Best Answer
Notes Recovery
The Easy Method
Notes: If
The Easy Method
works then the client can set up the phone from scratch and sign in with there email. The notes should sync.The Technical Method
The Hacking Method
Next Time
Make a backup in iTunes normally. Archive it. Make another backup
Make sure all notes are on iCloud or a Email Server
Use a Mac --> This ones just a preference :)