When you go to type in a name in the To: section, if there is an X button on the right side in the suggestion list, then it can be deleted from the history of recipients.
Otherwise, the unwanted contact must be deleted from your address book.

You can also adjust your suggested recipients list by going to Menu > Settings > Mail > Compose > Recipients history.