Addresses from a message in Messages or an email in the Mail app are not automatically stored in the Contacts app - this is so the info can either be Added to an Existing Contact, or used to Create a New Contact, or ignored altogether if you don't want it in Contacts.
Once an address has been entered, it is highlighted in blue. Click the name to open a drop-down menu that lets you decide what you want to do.
(Note that Mail does save/match email addresses from within the Mail app, but you have to consciously put them into Contacts if you want the address to be a contact. Could you imagine if every bit of spam you got was put into Contacts?)
