If you are storing contacts in more than one place, such as multiple email accounts as you have listed here, you need to go to Contacts, then in the upper left corner, make sure that you are looking at all of your Contact Groups. Also, when you go to Settings>Contacts, you can choose which account is going to be the default account that new contacts are saved in. If it were me, I would ensure that I have contacts all in a single account and make sure that you are backing them up on a regular basis. If you are using email accounts to handle your contacts, you can also turn them off/on in Settings, and you may wish to use a browser to log into the web access of your email account and verify what contacts are where.