It should be doing a partial string search on what you are typing against your entire contact list (and therefore give you a scrollable list of contacts to choose from that match your search so far). So if I start typing "Br" on my phone it would pop up all "Bryan Lastname" or "Firstname Bryant" in the suggestions list.

The 'Messaging' app only offers numbers with type "Mobile" as completions. This is unfortunate when you want custom labels for contacts with more than one mobile number.