Good idea, I tried adding accept_default="false", but it doesn't seem
to do anything (the first list entry is still picked, a bug regardless of the
search feature?).

Perhaps. We'll look into it.

I also tried combining this with force_select="true",
again no change.

BTW, having the default value for this and other param attributes as
another column in the table on the wiki would be a big help:
https://bitbucket.org/galaxy/galaxy-central/wiki/ToolConfigSyntax

We'll try to augment the wiki with this information soon.

I can insert a dummy entry at the start of my loc file like that, and then
I do see the "Click to Search or Select" text. However, the drop down
list includes the dummy entry - so this isn't a very good solution. I'd
need to add a validator to block the dummy entry or something, but
it would still be distracting.

This is the core problem. The prompt can only be presented when no choice is required; if a choice is required, then--like all select boxes--a default choice must be present. If a default choice is present, the prompt cannot be shown because the default choice must be shown.

There are definitely alternative approaches, such as putting a label next to the search+select that says "Click to Search or Select" or perhaps using a tooltip.

Currently my best workaround so far is to add a help attribute,
"When there are lots of entries, type here to search" (this needs
to be worded carefully as when there are only a few databases
setup you can't search).

Yes, this is in line with the label/tooltip solution. Additional suggestions are welcome as well.

P.S. I will still be checking email, but our Institute closes today for
the Christmas break, so I probably won't be able to try and code
changes immediately.

Happy Holidays!
J.