Version:            (using KDE KDE 3.4.0)

Adding a search box in the "open with..." dialog would be useful to narrow down the visible programs. If you know the program you want to use, you would type part of its name, and the list would be narrowed. Then you would click the program in the tree (which would probably become a flat list).

Note: the current text field is not the same thing, because you have to type the whole name, and because you don't have feedback (e.g. you are not told whether the program you typed is installed, is mistyped etc.)