Once you've sent an email to someone, Outlook remembers this and offers a list of suggested names each time you start typing in the address field.
Usually, this is very helpful but can sometimes be an issue if a recipient has changed their email address for some reason, as the stored address will be the old one and the mail will not be delivered to the new one. In cases such as this you will need to remove the old one from 'auto complete'. Normally this can be done by highlighting a name in the suggested list that pops up and pressing the 'delete' key on the keyboard (NOT the actual address in the address field). You then have to enter the new address either manually or from the address book.
If this doesn't work, then you will have to clear the whole 'AutoComplete cache' - the attached article walks you through the easy process of how to do this.