Enriquecarde, tu solucion requiere de macros:

Te explico la idea general, nada mas vamos por partes:

PARA ORDENAR TU BASE DE DATOS:
1. Necesitas una hoja que contenga la base de datos (registros)
2. Necesitas grabar una macro que se ejecute y ordene tus datos al momento de salir de la hoja, es decir, despues de que actualizas tus registros. (Puedes ejecutar tu macro mediante el Evento "Deactivate")

Insertas un Nombre de preferencia a la primera columna de tu base de datos, ejemplo "CLIENTE". Si quieres facilitarlo, a tu rango de nombre "CLIENTE" solo insertale una referencai absoluta, por ejemplo toda la columna BDCLIENTE!A:A. Esto tiene el inconveniente que tu lista siempre tendra todas las filas de excel.

PARA HACER UNA LISTA DESPLEGABLE:
Con la Caracteristica "Validacion..." NO ES POSIBLE hacer lo que pides, necesitas otro tipo de lista, debes usar el control llamado "Cuadro Combinado", lo encuentras en la barra de herramientas "Cuadro de Controles". Este tipo de controles si puede buscar los datos que coincidan mientras estas escribiendo.

Despues de insertar tu Cuadro combinado, le asignas en la propiedad "LinkedCell" la celda donde guardara el nombre del dato seleccionado, asigna en la Propiedad "ListFillRange" el nombre de tu lista, en el ejemplo "CLIENTE".
Una vez terminado, puedes escribir en tu cuadro combinado y notaras que mientras coincida con los registros de la lista, se iran cambiando.

Disculpa si no te doy el codigo VBA que desarrollé, pero prefiero que primero entiendas la idea general y lo intentes por ti mismo, ademas de que este espacio es pequeño para toda la explicacion.