1. A method of operating a wireless handheld device, comprising: upon receipt of a request to use a messaging service, displaying a recipient field for entering a recipient; upon detecting one keystroke of a key to which a first plurality of characters is assigned, displaying in the recipient field one of the first plurality of characters; upon detecting one keystroke of another key to which a second plurality of characters is assigned, displaying in the recipient field one of the second plurality of characters; looking up address book entries from an address book that match either of: the combination of two characters displayed in the recipient field; or any other combination of one of the first plurality of characters followed by one of the second plurality of characters; and displaying a selection menu of the matching entries.