Я не использую gnome ATM, но для этого были сделаны небольшие исследования для gnome3:
Install dconf-tools. Run dconf Editor and navigate to /desktop/unity/runner/history
(с http://www.techques.com/question/24-122473/Delete -Alt-F2-история)