Shuttleworth: Amazon search results in the Dash

Actually, that one might just be a sensible way to do it.
After all, Ubuntu's command-not-found is actually quite helpful, telling you the apt-get command you need to run.

I'd have no objection to that instance, provided that I had already chosen to add the commercial repository to apt, and that the query was a local one, matching against a local list of available packages (rather than sending the full text of any potentially mis-spelled command + args over the net to a 3rd party).