From my research, it looks like the Listbox enables UI virtualization by default. It didn't help. I ended up finding some helpful soul's NavigationListControl and limiting the number of results until the user taps a "show all" button. It helped a little. I think the final solution will be pre-allocating the first N data items with empty strings so that the initial cost of the Listbox is incurred at initial-page-layout-time rather than at keypress-time.
I was solving similar problem but with a datagrid. I ended up adding my own scrollbar (so that I have better knowledge of what to preload) and populating the datagrid with an array of references to a single "Loading" object. The reduction in allocations sped it up a lot as well, I guess.
