With about 60 applications on my USB key here are some important improvements needed:
1. A search like Vista's start menu or Kickoff menu (see below).
2. Categorize content
3. More functions like the Kickoff menu of OpenSUSE.
The Kickoff Start Menu is the new start menu of OpenSUSE which impressed me a lot because it provides fast access to everything. Here's a screen-shot:
It has tabs (for favorite, all applications, system commands...) and search. Most functionalities could be used for a portable menu.
Head to the search box (above right hand corner) and look for geek.menu. It might not be what you are looking for, but it is a fork of the portableapp.com menu. It's developer has integrated a search box into his version.