I just pushed out an update to gitk that adds a new feature: under the File menu there is now a "List references" entry that pops up a window containing a list of the heads, tags and other references that appear in the graph pane, sorted by name. Clicking on a list entry selects that commit in the main window.
Paul.