I don't know how hard this would be or if it's "feasibly" possible. Currently, I believe, in order to remove (even add) links to the menu, you must do it in each theme (and/or the language files). This is fine if you have a default theme that isn't user changeable.
Maybe some radio buttons to enable / disable certain menu items (ie, uncheck showing the "search" link - ie, not required). Maybe even a field to add custom links. I haven't studied this yet, just thought of it. Not trying to add work for you devs, maybe 1.5?
Just throwin' it out there for consideration.