There should be a dialog box which would propose to install the software (or possibly one in a list).
For example:
* One hits Alt+F2 and tries to execute the command gimp
* On Lucid, this command has disappeared by default
* A dialog box pops-up and says :
"The program Gimp isn't installed yet on your system, but is provided by the package 'gimp'. Do you want to install and execute it now ?"
* If the user clicks on yes/Ok, a summary of installations is shown.
* Then apt-get installs the package and launches the command gimp.
What's more, if nothing was found on the repository, there should be a message either :
* inviting the user to search on ubuntu documentation sites for an alternative repo or way of installation.
* or listing command names which could have been misspelled.
This would have several benefits on well known softwares :
* No need to launch synaptic, or software store
* No need to perform a search
* A disappeared software from a new release of ubuntu could be quickly installed again.
* In general, a better information given to the user and a better user experience.
* Extend the system in place for codec/drivers/language/ff plug-ins to software and gain in homogeneity.
[PS] Excuse my bad English, I'm French and if I made mistakes, please mention it, thanks !
