Пускай программа сама ищет по всему дереву сразу. Т.е. я ввел три буквы - она нашла первую подходящую ветвь и установила на нее курсор. Я нажал стрелку вниз - она нашла следующую (не обязательно у того же самого родителя!) и поставила курсор на нее. И т.д.
Фактически, при таком подходе отличие от описанного мною выше варианта будет только в том, что в выпадающем списке не будет уменьшаться число элементов (оно наоборот будет увеличиваться по мере того, как все новые и новые узлы дерева будут раскрываться).
На мой взгляд, такое поведение, хотя и будет большим шагом вперед, все же не очень удачно с т.зр. usability. Во-первых, когда ты видишь в списке всего 3 варианта, сориентироваться гораздо проще, чем когда их всегда будет около десятка (т.е. я за фильтрацию). А во-вторых, при очень "густых" деревьях и теперешнем способе их отображения не всегда будет просто сориентироваться, а где же именно мы сейчас находимся - скорее всего, бОльшая часть родительских узлов (если не все) не будут видны. И чтобы определить текущий контекст, придется тянуться за мышкой, целиться в скролбар и тащить его вверх.
 
В общем, я считаю наиболее удачным с т.зр. юзабилити именно последний предложенный мною вариант (с путем к узлу в скобках). Первый несколько проигрывает тем, что названия узлов не выровнены по левому краю - соответственно, приходится "бегать глазами", когда просматриваешь список.