I agree, I've been seeing this in other places as well. I can't recall where I saw it but I was using my iPod touch and saw some autocompletion list use ellipsis in the middle and thought it was brilliant.

When using long titles the beginning will be the same, especially knowing that our list will be in alphabetical order (as opposed to search rank or whatever, which is what a search engine's suggestions would/could be) it is very likely and worth optimizing for.

Sounds like a good feature to implement in the jquery.autoEllipsis plugin we maintain in MediaWiki.

Already fixed in master.