If you're doing a StartsWith, perhaps you could break the list down into sub-lists, which obviously would take time, but it wouldn't be time that a human would wait on, since it could be done in the background. Then you could have a list for each letter of the alphabet (or break it down more for common letters and group a few common ones together, whatever works to break it down most evenly).
It wouldn't be 'elegant' to have a bunch of switch statements for each starting letter, but you could easily trim the list length from 600k to sort through to 60k or less, which would drastically reduce the time required to return results.
Alternatively, another option would be to change your datatype entirely. You could pre-sort your 600k list into
Dictionary<string, List<string>> with the key being a string of the "StartsWith" you want to match. Then modify your code to simply pull the list stored as the value in the dictionary that matches your StartsWith. So, if you pre-sort to 2 letters, such as aa, ab, ac, ad, etc etc, once you match that, you get can then sort through a drastically smaller list. You could even pre-sort to 3 letters, such as aaa, aab, aac, and so on, which should result in needing to parse through a list of probably under 1000 elements for the longest list in the dictionary, with many being significantly smaller than 1000.
Using a 3-letter key would result in a dictionary with around 17k keys, which should yield acceptable performance. Accessing the dictionary value should be well under 1ms, then sorting through a list with under 1000 elements should be under 10ms, which should result in your function returning a value in more like 20ms rather than 2 seconds. The downside would be needing to break apart your 600k element list into 17,576 smaller sorted lists, then storing each of those in a dictionary with the appropriate "StartsWith" key. This, however, should only take a few seconds and can be done at initialization (and new entries for your list, which I assume isn't static, can be added to the dictionary rather than the jumbo-list, resulting in only needing to sort the list once, ever).
The best bet would be a database, but since that's not an option for you, the second-best thing would be simply reducing the length of your list from 600k down to something much much smaller.