Thanks for the ideas. I went with a seperate lookup table that is maintained by the parent table (PK on id) through some triggers. This let me set a PK on the name+id. I'm just bringing back 150 records on each keystroke and since the PK holds an alpha sort, I get back what I need and in the right order. And it's fast enough that you just see a slight hesitation after each keystroke.
I know that, at some point, some user is going to scroll down more than 15 times and call our help desk wondering where the rest of the list is. It's the best I could do.