I'm going to try something before getting too much further along developing it. I'm making a backup copy of the message table and will full-index it using a descending-order key on message number as the unique identifier then benchmark searches on it. I'm finding that performance when sorting messages in ascending order is pretty darned good, but descending order is what we'd usually use. So I'll see if a fulltext index that's built in descending order might help.