Q: Lost notes after update to IOS 9.3.4 - Not enough space to restore back up

Hello and welcome to Apple Support Communities, jozephus! 

If I’m understanding your post right, after updating to iOS 9.3.4 from iOS 7, all of your notes no longer appear in the Notes app and you're not able to restore your backup via iTunes due to a lack of space. I usually keep a lot of important  data in the Notes app on my iPhone so I can certainly understand why it would be a problem not having access to it. I'm happy to help you get this sorted out!

It's very likely that you're getting the error in iTunes when trying to restore your backup simply because the backup itself, along with iOS 9, are too large for the capacity of your iPhone. Since restoring from an iTunes backup removes everything from your iPhone and replaces it with the contents of the backup, deleting things currently on your iPhone in an attempt to make more room for the backup would unfortunately not help. So to answer your first question, yes, it's possible that your iPhone 5 backup is too big to fit on your iPhone now that you have upgraded your iOS. 

There is no Apple approved way to reduce the size of an iTunes backup or to restore only part of your iTunes backup to your device. There are different third-party software out there, like the one you mentioned, that do claim to extract data from backups but there is always a chance of damaging the files within your backup when doing so, therefore we don't recommend it.

You mentioned that you never use iCloud but it’s still a good idea to check to make sure none of those notes synced to iCloud at any point. To check to see if they were synced with iCloud, log into https://www.icloud.com. Once logged in, click on the Notes icon. If you see your notes there, go to Settings > iCloud on your iPhone and enable Notes. Your Notes should then begin to sync back to your phone. 

You also mentioned that when you open your Notes app, you see a folder named "Outlook". This means that it may be possible your notes were actually syncing with one of your email accounts. To check to see if this is true, log into your email accounts online and see if your notes are in the Notes section there. If they are, you will simply need to sign into that email account on your phone, if you aren't already signed in, and then enable Notes syncing. The article below will show you how to sign into your email account if you aren't familiar with the steps. Once you're signed into the email account, go to Settings > Mail, Contacts, Calendars, tap on the email account there and enable Notes to have them sync back up. 

Set up an email account on your iPhone, iPad, or iPod touch

Since there have been many changes to iOS since iOS 7, I have provided the iOS 9 iPhone user manual below.

iPhone User Guide

Thanks for using Apple Support Communities. 

Take care!

If your notes are in your Outlook account, whether or not you have been able to figure out how to view them online, you should be able to sync the notes back to your iPhone. In order for them to sync, your Outlook email would need to be set up as an Exchange account in your Mail app. More than likely, you will have to set it up manually using your email account server settings. Below, you will find a link to steps from Microsoft on how to set up the account in your phone, as well as a link to our Mail Settings Lookup tool. During the setup process, you will be given a chance to choose which content you want to sync and Notes should be one of the options. 

Outlook: Set up Microsoft Exchange email on Apple iPhone, iPad, or iPod touch

Apple: Mail Settings Lookup

If your Outlook is already set up in your iPhone as an Exchange account, let’s try forcing it to sync. First, make sure that Notes syncing is not enabled for any other accounts. To do this, go to Settings > iCloud and disable Notes there if it's enabled. Also, go to Settings > Mail, Contact, Calendars, tap on each one of your email accounts you have set up and disable Notes, including your Outlook email account. Next, force close the Notes app using the steps in the following support article: Force an app to close on your iPhone, iPad, or iPod touch After that, tap on your Outlook email account in Mail, Contacts, Calendars, and re-enable Notes. Give it a few minutes before you open up the Notes app again to check if any have appeared. 

Take care!

Hello again, jozephus. 

That third-party app is more than likely not finding any notes on your iPhone because the notes were somehow removed. There isn't a chance they are just hiding on your iPhone somewhere; they are either on the phone or they aren't. With the troubleshooting I had you do, we were trying to hopefully sync those notes back to your phone. It doesn't appear that the notes were syncing with your Outlook account since they are not synching back.

If you had any other email accounts set up on your iPhone that allow Notes syncing, you can try going to Settings > Mail, Contacts, Calendars, tap on each email account one at a time, and enable Notes syncing. You would want to give the phone time to try and sync those notes back before trying another email account in your device. Before enabling Notes on another account, make sure you disable Notes in the same place in Settings for the email accounts you have already tried. 

If you or any friends or family members have an iPhone that is larger than 16GB, another option may be to use their device to recover your missing notes. It's a little bit more time consuming but could be worth it to get your notes back. First, you would want to have them back up their device. Once it's backed up, they would then want to restore their iPhone from the iTunes backup you created using your phone before you lost your notes. After their device is restored, have them email the notes to you from the Notes app. When the notes are safely on your iPhone again, your friend/family member can then restore their device again from backup, but this time they will use their own backup. If you go with this option, make sure when they back up their iPhone and restore it from their own backup, they use their own computer so that their iTunes Music syncs back to their iPhone afterwards since iTunes music is not included in backups. 

How to back up your iPhone, iPad, and iPod touch

Import photos and videos from your iPhone, iPad, or iPod touch

iPhone User Guide: Organize and share notes

Restore your iPhone, iPad, or iPod touch from a backup

You’re also more than welcome to explore those third-party apps to see if they are successful in getting your notes back too. Just keep in mind though, as I mentioned in the reply to your initial post, you run a risk of files being damaged within your backup any time you use non-Apple authorized software to extract data from a backup.

Have a great rest of your weekend!