Would it be possible to add a search feature of entering text in order to jump to a particular message? Start typing, and as you do, the list filters based on that? This would seem to not conflict with any design premise and not require an interface change.