Hola, el estropajo es el AJAX. Nose exactamente qué es, me suena que es algo como que se puede combinar javascript con PHP, pero no me hagas mucho caso.
En cuanto a lo de autocompletar, claro que se puede, pero me temo que has de poner todos los datos en el código fuente, y cuando quieres añadir o modificar debes editar la página y modificar el código. En la página que mencionas todos los datos que aparecen en el menú emergente están en código en la página
http://www.mexicana.com/g5tx/js/queryAirports_es.js
Si ves el código fuente ves todo redactado. Si se pueden descargar todos esos datos desde una base de datos para crear esa página, creo que no, pero si es así, ojalá venga alguien y nos ilumine.
También puedes echarle un vistazo al post de la maravillosa Tunait.
http://www.forosdelweb.com/f13/generador-menus-desplegables-180129/