You're in luck. The Run Command dialog box (yes, that is its name) is being totally re-written in KDE 4, and that is one of the features that it will have if I remember correctly. Now, all that's left is to wait for KDE 4.0 to come out.
In the mean time, might I interest you in taking a look at this, imho, wonderful KDE launcher, which has the feature you are asking for, and more:
http://katapult.kde.org/